Seminar of Graph Theory - Jean Paul Zerafa (4.11.2021)
Thursday 4.11.2021 at 9:50, Lecture room M/213
Jean Paul Zerafa:
Hamiltonicity, k-factors and colourings: some open problems
Abstract:
In this talk we shall discuss some open problems I encountered in the last couple of years. Most of these deal with Hamiltonian cycles, k-factors (k-regular spanning subgraphs), and edge- or vertex-colourings of graphs. The first problem states that every bridgeless cubic graph G admits two 1-factors (perfect matchings) whose deletion leaves a bipartite subgraph of G. This is known as the S4-Conjecture (Mazzuoccolo, 2013) and would be true if the Berge– Fulkerson Conjecture is true. Another problem is a conjecture by Funk, Jackson, Labbate and Sheehan, from 2003, dealing with 2-factor Hamiltonian graphs (each 2-factor in such graphs is a Hamiltonian cycle). They conjecture that every bipartite cubic 2-factor Hamiltonian graph can be obtained from the complete bipartite graph K3,3 and the Heawood graph by using a graph operation known as the “star product”. We shall also discuss a recent conjecture by Ban and Linial about 2-bisections, which are 2-vertex-colourings (not necessarily proper) of graphs such that the two colour classes have the same cardinality and the monochromatic components are either a single vertex or an edge. In 2016, they conjectured that every bridgeless cubic graph, except the Petersen graph, admits a 2-bisection. Finally, if time permits, we shall also talk about clique-decompositions and particular edge-colourings of the complete graph. The scope of this talk is to give a brief overview of these problems and suggest specific research routes that could be taken, hoping that this would lead to collaboration and work whilst in Bratislava.