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

József Balogh, János Barát, Dániel Gerbner, András Gyárfás, Gábor N. Sárközy

Research output: Contribution to journalArticle

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 (Formula Presented.) can be covered by the vertices of two vertex disjoint monochromatic cycles of distinct colors. Finally, under the assumption that (Formula Presented.) 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.

Original languageEnglish (US)
Pages (from-to)507-526
Number of pages20
JournalCombinatorica
Volume34
Issue number5
DOIs
StatePublished - 2014

Keywords

  • 05C15
  • 05D10

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Computational Mathematics

Fingerprint Dive into the research topics of 'Partitioning 2-edge-colored graphs by monochromatic paths and cycles'. Together they form a unique fingerprint.

  • Cite this

    Balogh, J., Barát, J., Gerbner, D., Gyárfás, A., & Sárközy, G. N. (2014). Partitioning 2-edge-colored graphs by monochromatic paths and cycles. Combinatorica, 34(5), 507-526. https://doi.org/10.1007/s00493-014-2935-4