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\alpha (G)$ monochromatic cycles, where $\alpha (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 $(1+\eps){3|V(G)|\over 4}$ can be covered by the vertices of two vertex disjoint monochromatic cycles of distinct colors. Finally, under the assumption that $\overline{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_4)=1$, which is best possible.

References in corpus (1)

• Monochromatic cycles and the monochromatic circumference in 2-coloured graphs

Cited by in corpus (10)

• Vertex covers by monochromatic pieces - A survey of results and problems
• Local colourings and monochromatic partitions in complete bipartite graphs
• Monochromatic cycle partitions in random graphs
• Ramsey number of a connected triangle matching
• Monochromatic cycle covers in random graphs
• Almost partitioning a 3-edge-coloured $K_{n,n}$ into 5 monochromatic cycles
• Large monochromatic components in expansive hypergraphs
• Ore- and Pósa-type conditions for partitioning $2$-edge-coloured graphs into monochromatic cycles
• Partitioning a 2-edge-coloured graph of minimum degree $2n/3+o(n)$ into three monochromatic cycles
• Partitioning edge-coloured complete graphs into monochromatic cycles and paths