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

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'ark"ozy: 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(\mathrm{\mid }V(G)\mathrm{\mid })$ vertices, the vertex set of any $2$-edge-colored graph $G$ with minimum degree at least $(1+\text{eps})\frac{3\mathrm{\mid }V(G)\mathrm{\mid }}{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$, $\mathrm{\mid }V(G)\mathrm{\mid }-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.