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

DOI10.1007/S00493-014-2935-4zbMATH Open1340.05069arXiv1509.05544OpenAlexW2047807138MaRDI 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)

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.

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

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

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)

Cites Work

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

Cited In (27)

• Large monochromatic components in edge colored graphs with a minimum degree condition
• Ramsey number of paths and connected matchings in Ore-type host graphs
• Embedding Graphs into Larger Graphs: Results, Methods, and Problems
• Minimum degree conditions for monochromatic cycle partitioning
• Vertex covers by monochromatic pieces -- a survey of results and problems
• Monochromatic cycle partitions of graphs with large minimum degree
• Improved monochromatic loose cycle partitions in hypergraphs
• Partitioning a graph into a cycle and a sparse graph
• Almost Partitioning a 3-Edge-Colored $K_{n,n}$ into Five Monochromatic Cycles
• Monochromatic bounded degree subgraph partitions
• Monochromatic cycle partitions of \(2\)-coloured graphs with minimum degree \(3n/4\)
• 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
• Large monochromatic components in expansive hypergraphs
• The complexity for partitioning graphs by monochromatic trees, cycles and paths
• Local colourings and monochromatic partitions in complete bipartite graphs
• Vertex covering with monochromatic pieces of few colours
• Partitioning 2-edge-colored Ore-type graphs by monochromatic cycles
• Monochromatic square-cycle and square-path partitions
• Stability for vertex cycle covers
• Almost partitioning 2-edge-colourings of 3-uniform hypergraphs with two monochromatic tight cycles
• Monochromatic cycle power partitions
• Shortcutting directed and undirected networks with a degree constraint
• Partitioning random graphs into monochromatic components
• Partitioning edge-coloured infinite complete bipartite graphs into monochromatic paths
• Monochromatic cycle partitions in random graphs
• Two-coloring the edges of a cubic graph such that each monochromatic component is a path of length at most 5

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)