Monochromatic cycle partitions of 2-coloured graphs with minimum degree 3n/4

2015/02/26 by Letzter, Shoham · 1 citation
#05C38 #05C55 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1502.07736

Abstract

Balogh, Barát, Gerbner, Gyárfás, and Sárközy proposed the following conjecture. Let G be a graph on n vertices with minimum degree at least 3n/4. Then for every 2-edge-colouring of G, the vertex set V(G) may be partitioned into two vertex-disjoint cycles, one of each colour. We prove that this conjecture holds for n large enough, improving approximate results by the aforementioned authors and by DeBiasio and Nelsen.

Cited by

• Monochromatic cycle partitions in 3-mean edge-colourings

Related

• Partitioning a 2-edge-coloured graph of minimum degree 2n/3 + o(n) into three monochromatic cycles
• Minimum degree conditions for monochromatic cycle partitioning
• Monochromatic cycle partitions of graphs with large minimum degree
• Partitioning 2-edge-coloured bipartite graphs into monochromatic cycles
• Partitioning a graph into monochromatic connected subgraphs