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

DOI10.1007/S00493-014-2935-4zbMATH Open1340.05069OpenAlexW2047807138MaRDI QIDQ484546FDOQ484546

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

Publication date 7 January 2015

Published in Combinatorica (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1509.05544

zbMATH Keywords

proper 2-coloringtriangulation of a sphere

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Algebraic combinatorics (05E99) Ramsey theory (05D10) Triple systems (05B07)

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'ark"ozy: the vertex set of every $2$-edge-colored graph can be partitioned into at most $2alpha(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)|over4$ can be covered by the vertices of two vertex disjoint monochromatic cycles of distinct colors. Finally, under the assumption that $overlineG$ 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.

Recommendations

• Triangulations of the sphere, bitrades and abelian groups
• Balanced polychromatic 2-coloring of triangulations
• Latin trades in groups defined on planar triangulations
• Partitioning 2-edge-colored Ore-type graphs by monochromatic cycles
• scientific article; zbMATH DE number 1123793

Cites work

• scientific article; zbMATH DE number 3641497 (Why is no real title available?)
• scientific article; zbMATH DE number 878896 (Why is no real title available?)
• scientific article; zbMATH DE number 5174567 (Why is no real title available?)
• scientific article; zbMATH DE number 3215865 (Why is no real title available?)
• An improved bound for the monochromatic cycle partition number
• Covering Two-Edge-Coloured Complete Graphs with Two Disjoint Monochromatic Cycles
• Gallai colorings and domination in multipartite digraphs
• Gallai colorings of non-complete graphs
• Monochromatic Hamiltonian Berge-cycles in colored complete uniform hypergraphs
• Monochromatic cycle partitions of edge-colored graphs
• Monochromatic cycles in 2-coloured graphs
• On 2-factors with \(k\) components
• On a problem of K. Zarankiewicz
• On maximal paths and circuits of graphs
• Partitioning 3-colored complete graphs into three monochromatic cycles
• Partitioning 3-coloured complete graphs into three monochromatic paths
• Partitioning Two-Coloured Complete Graphs into Two Monochromatic Cycles
• Partitioning a graph into a cycle and an anticycle, a proof of Lehel's conjecture
• Partitioning edge-coloured complete graphs into monochromatic cycles and paths
• Path-cycle Ramsey numbers
• Some Ramsey-Turán type problems and related questions
• Star versus two stripes Ramsey numbers and a conjecture of Schelp
• Three-color Ramsey numbers for paths
• Tripartite Ramsey numbers for paths
• Vertex coverings by monochromatic cycles and trees
• Vertex coverings by monochromatic paths and cycles
• \(R(C_n,C_n,C_n)\leqq (4+o(1))n\)

Cited in

(29)

• Minimum degree conditions for monochromatic cycle partitioning
• Almost partitioning a 3-edge-colored \(K_{n,n}\) into five monochromatic cycles
• Monochromatic cycle partitions of \(2\)-coloured graphs with minimum degree \(3n/4\)
• Improved monochromatic loose cycle partitions in hypergraphs
• Partitioning a graph into a cycle and a sparse graph
• Partitioning a 2-edge-coloured graph of minimum degree \(2n/3 + o(n)\) into three monochromatic cycles
• Two-coloring the edges of a cubic graph such that each monochromatic component is a path of length at most 5
• Growth rates of groups associated with face 2-coloured triangulations and directed Eulerian digraphs on the sphere
• Vertex covers by monochromatic pieces -- a survey of results and problems
• Stability for vertex cycle covers
• Almost partitioning 2-edge-colourings of 3-uniform hypergraphs with two monochromatic tight cycles
• Embedding Graphs into Larger Graphs: Results, Methods, and Problems
• Monochromatic cycle power partitions
• The complexity for partitioning graphs by monochromatic trees, cycles and paths
• Vertex covering with monochromatic pieces of few colours
• Partitioning 2-edge-colored Ore-type graphs by monochromatic cycles
• Monochromatic cycle partitions of graphs with large minimum degree
• Local colourings and monochromatic partitions in complete bipartite graphs
• Large monochromatic components in expansive hypergraphs
• Large monochromatic components in edge colored graphs with a minimum degree condition
• Monochromatic square-cycle and square-path partitions
• Triangulations of the sphere, bitrades and abelian groups
• Monochromatic cycle partitions in random graphs
• Shortcutting directed and undirected networks with a degree constraint
• Partitioning random graphs into monochromatic components
• Ramsey number of paths and connected matchings in Ore-type host graphs
• Partitioning edge-coloured infinite complete bipartite graphs into monochromatic paths
• Monochromatic bounded degree subgraph partitions
• Ore- and Pósa-type conditions for partitioning 2-edge-coloured graphs into monochromatic cycles

This page was built for publication: Partitioning 2-edge-colored graphs by monochromatic paths and cycles

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q484546)