Ljubljana - Leoben Graph Theory Seminar 2014

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:

• 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 CI-groups 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 well-covered 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 edge-transitive 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 CI-groups 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 CI-graph 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 DCI-group if every Cayley graph of G is a CI-graph, and it is called a CI-group if every undirected Cayley graph of G is a CI-graph (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 CI-groups (Li-Lu-Pá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 Yan-Quan 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 2-colouring, if every non-trivial 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 non-trivial automorphism moves at least 2log(|AutG|) vertices, then there is a distinguishing 2-colouring. 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 non-mainstream but interesting edge-colouring 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 Hung-Lin Fu, dubbed this number the excessive factorization index of a graph. Its computation is an NP-complete 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 NP-complete 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 edge-colouring problem can be solved in polynomial time for any given constant B: given a simple graph G, find an edge-colouring 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 edge-coloring result went on Algorithmica and, if that will fit the time-slot, 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.