Seminár z teórie grafov - Leonard Chidiebere Eze (2.12.2021)

vo štvrtok 2.12.2021 o 9:50 hod. online formou

30. 11. 2021 14.04 hod.
Od: Martin Škoviera

Prednášajúci: Leonard Chidiebere Eze

Názov: Expander Graph Constructions

Termín: 2.12.2021, 9:50 hod., MS Teams 

Pristupový kód do MS TEAMS je: gglxxc7
(pre účastníkov z UK v Bratislave)

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.

Stránka seminára