Partitioning 2-edge-colored graphs by monochromatic paths and cycles

Abstract

We present results on partitioning the vertices of 2-edge-colored graphs into monochromatic paths and cycles. We prove asymptotically the two-color case of a conjecture of Sárközy: the vertex set of every 2-edge-colored graph can be partitioned into at most 2α(G) monochromatic cycles, where α(G) denotes the independence number of G. Another direction, emerged recently from a conjecture of Schelp, is to consider colorings of graphs with given minimum degree. We prove that apart from o(|V (G)|) vertices, the vertex set of any 2-edge-colored graph G with minimum degree at least $\tfrac{{(1 + \varepsilon )3|V(G)|}} {4}$can be covered by the vertices of two vertex disjoint monochromatic cycles of distinct colors. Finally, under the assumption that $\bar G$ does not contain a fixed bipartite graph H, we show that in every 2-edge-coloring of G, |V (G)| − c(H) vertices can be covered by two vertex disjoint paths of different colors, where c(H) is a constant depending only on H. In particular, we prove that c(C ₄)=1, which is best possible.