2014/08/20 by József Balogh, Jozsef Balogh, Janos Barat +7 · 36 citations
Computer Science · Mathematics · #Bipartite graph #Colored #Combinatorics #Conjecture #Discrete mathematics #Disjoint sets #Edge coloring #Graph #Graph Labeling and Dimension Problems #Graph power #Graph theory and applications #Independence number #Limits and Structures in Graph Theory #Line graph #Mathematics #Monochromatic color #Physics #Vertex (graph theory) #math.CO #msc:05C15
paper · pdf · doi:10.1007/s00493-014-2935-4
published in COMBINATORICA 34(5), 507-526 (Springer Science+Business Media)
openalex publication_date 2014/08/20 · arxiv created 2015/09/18 · arxiv updated 2015/09/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
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 (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 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(C4)=1, which is best possible.