Seminar of Graph Theory - Leonard Chidiebere Eze (2.12.2021)
Thursday 2.12.2021 at 9:50, online
Leonard Chidiebere Eze:
Expander Graph Constructions
Access code for MS TEAMS je: gglxxc7
(Access code for Comenius University only)
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.