35 September 2014
UP FAMNIT, Koper, Slovenia
Europe/Ljubljana timezone
Scientific Programme
Ljubljana  Leoben Graph Theory Seminar 2014 is an international workshop in a series of seminars traditionally connecting the Austrian and the Slovenian graph theory communities. It gives an opportunity to participants to present latest advances in all areas of Graph Theory.
Timetable (pdf)
The following invited speakers have confirmed their participation:
Abstracts of invited talks:
Minimum Maximal Matching: old problem, new challenges
Tinaz Ekim, Boğaziçi University, Istanbul, Turkey
Alexander Ivanov, Imperial College London, United Kingdom
Elena Konstantinova, Novosibirsk State University, Sobolev Institute of Mathematics, Novosibirsk, Russia
István Kovács, University of Primorska, Koper, Slovenia
Florian Lehner, TU Graz, Austria
Romeo Rizzi, University of Verona, Italy
Timetable (pdf)
The following invited speakers have confirmed their participation:

Tinaz Ekim, Boğaziçi University, Istanbul, Turkey
Talk title: Minimum Maximal Matching: old problem, new challenges 
Alexander Ivanov, Imperial College London, United Kingdom
Talk title: Revisiting Goldschmidt's Amalgams 
Elena Konstantinova, Novosibirsk State University, Sobolev Institute of Mathematics, Novosibirsk, Russia
Talk title: Hamiltonicity of graphs and Gray codes 
István Kovács, University of Primorska, Koper, Slovenia
Talk title: Finite CIgroups and Schur rings 
Florian Lehner, TU Graz, Austria
Talk title: Symmetry breaking in graphs and groups 
Romeo Rizzi, University of Verona, Italy
Talk title: Covering the edges of a graph by matchings of bounded size
Abstracts of invited talks:
Minimum Maximal Matching: old problem, new challenges
Tinaz Ekim, Boğaziçi University, Istanbul, Turkey
Given a graph G, the problem of finding the minimum size maximal matching (MMM) is also known as the (independent) edge dominating set (EDS) in the literature. This problem, as well as several closely related problems, have been studied in the literature from several aspects such as computational complexity in special graph classes, approximation, exact solution procedures with experimental results etc. Structural properties related to MMM such as equimatchable and wellcovered graphs are also well studied. In this talk, we will first mention some recent results related to MMM and then point out several current research directions and open questions.Revisiting Goldschmidt's Amalgams
Alexander Ivanov, Imperial College London, United Kingdom
Let Γ be a finite cubic graph, let G be an edgetransitive automorphism group of Γ, let {x,y} be an edge of Γ, and let A = {G(x),G(y)} be the amalgam formed by the corresponding vertex stabilizers. In a groundbreaking paper of 1980 D.M.Goldschmidt proved that G(x) = G(y) divides 27 3 and that there are exactly fifteen possibilities for the isomorphism type of A. I am planning to discuss the structure of the Godlschmidt amalgams with a particular emphasis on the largest one, embedded into the automorphism group Aut(M12) of the sporadic Mathieu group M12.Hamiltonicity of graphs and Gray codes
Elena Konstantinova, Novosibirsk State University, Sobolev Institute of Mathematics, Novosibirsk, Russia
In this talk we consider the hamiltonian problem for Cayley graphs having hierarchical structure (such as the hypercubes, the Pancake graphs, the Star graphs). Approaches and algorithms for getting hamiltonian cycles and paths are given. The connections to Gray codes are illustrated. Open problems are also discussed.Finite CIgroups and Schur rings
István Kovács, University of Primorska, Koper, Slovenia
For a finite group G and a subset S of G such that 1 is not in S the Cayley graph Cay(G,S) has vertex set G and arcs in the form (x,sx) where x runs over G and s runs over S. A Cayley graph Cay(G,S) is called a CIgraph if for every subset T with Cay(G,T) being isomorphic to Cay(G,S), T=f(S) for some automorphism f of G. The group G is called a DCIgroup if every Cayley graph of G is a CIgraph, and it is called a CIgroup if every undirected Cayley graph of G is a CIgraph (note that, Cay(G,S) is undirected when the set S is closed under taking inverse elements). Although there is a restrictive list of potentional CIgroups (LiLuPálfy, 2007), only a few classes of groups have been proved to be indeed CI; in several cases the proof was obtained by studying the Schur rings over the given group. In my talk I review the Schur ring method and also present some recent results based on a joint work with YanQuan Feng (Beijing Jiaotong University, China).Symmetry breaking in graphs and groups
Florian Lehner, TU Graz, Austria
Call a colouring of a graph distinguishing if it is only preserved by the identity automorphism. Tucker conjectured that there is a distinguishing 2colouring, if every nontrivial automorphism of a graph moves infinitely many vertices. While the general conjecture is still wide open, the statement is known to be true for many special graph classes. It also compares to a result for finite graphs: If every nontrivial automorphism moves at least 2log(AutG) vertices, then there is a distinguishing 2colouring. We give an overview of recent progress towards Tucker’s conjecture, show how probabilistic methods can be used to simplify many proofs, and highlight some open research problems.Covering the edges of a graph by matchings of bounded size
Romeo Rizzi, University of Verona, Italy
Our aim in this talk is to report on a nonmainstream but interesting edgecolouring line of research we were conducting with our coauthor, friend, and colleague, David Cariolaro, prematurely disappeared this January. For me, the talk is also a tribute to David's memory. Yet, I (and David) would hope this to be a lively talk where the few techniques and results we could gather together get exposed, and new agendas of curiosity and enquiry are drawn. A problem he loved: what is the minimum number of perfect matchings which allows to cover every edge of a graph? He, with HungLin Fu, dubbed this number the excessive factorization index of a graph. Its computation is an NPcomplete problem and interesting families of regular graphs where this number goes big where described by other authors. A more pratically oriented problem: what if we are allowed to use only matchings of size at most (or precisely) a fixed given natural B? He dubbed this number the excessive (B)factorization index (the excessive [B]factorization index, resp.) of a graph. Bipartite graphs: though all of the above factorization indices are NPcomplete to compute, together (2010) we gave effective polynomial time algorithms for their determination in the bipartite case. These algorithms work also for multigraphs (parallel edges) and the dependence of their running times in B is also polynomial. Classical edge coloring with color classes of bounded size: in a joint technical paper on Algorithmica (2014), we showed that the following fundamental edgecolouring problem can be solved in polynomial time for any given constant B: given a simple graph G, find an edgecolouring of G where each colour is assigned to at most B edges and which, subject to this condition, has the fewest number of colour classes. Though the running time of these algorithms is high (with polynomials in B at the exponent), this is yet a novel piece of good news in the realm of edge colouring, and should motivate for more investigations to follow. Current results: the algorithm in the paper went on Algorithmica can be further developed in order to provide, for any fixed B, a polynomial time algorithm for the computation of the excessive (B)factorization index and of the excessive [B]factorization index of any simple graph. Last year we submitted a work on this, that this summer got accepted by JGT. In the talk, I would like to expose the technical edgecoloring result went on Algorithmica and, if that will fit the timeslot, also its extension to the computation of the factorization indexes. In the talk or in discussions to follow, I would also like to share the sidepath problems we left open.