Graph Theory Seminar: “Minimum degree threshold for covering bipartite graphs with monochromatic components”

Abstract:

Covering the vertices of edge-coloured graphs with monochromatic components has been a beloved pastime of combinatorialists for decades, largely motivated by a celebrated conjecture of Ryser. Some years ago, Bal and DeBiasio inquired about the minimum degree threshold that guarantees that the vertex set of an r-edge-coloured graph can be covered with at most r monochromatic components. This question has since led to many more related problems and accompanying results. Most notably, Girao, Letzter and Sahasrabudhe proved that every large enough n-vertex 2-edge-coloured graph with minimum degree exceeding (2n-5)/3 can be covered with at most two monochromatic components.

In a recent paper, Fernandez, Pavez-Signe and Stein worked on an analogous problem for bipartite graphs. Namely, they proved that every large enough 2n-vertex, 2-edge-coloured, balanced bipartite graph with minimum degree at least (13/16 + ε)n can be covered with at most three monochromatic components. That said, they expected the threshold to be around 2n/3. In this talk, I will prove that they were right.

This is joint work with Cesar Bispo, Marcelo Lage, Guilherme Mota and Bruno Skarmeta.

Speaker: George Kontogeorgiou (CMM)