Partitioning edge-coloured complete graphs into monochromatic cycles and paths
From MaRDI portal
Publication:402591
DOI10.1016/J.JCTB.2014.01.003zbMATH Open1300.05260arXiv1205.5492OpenAlexW2051205297MaRDI QIDQ402591FDOQ402591
Authors: Alexey Pokrovskiy 
Publication date: 28 August 2014
Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)
Abstract: A conjecture of ErdH{o}s, Gy'arf'as, and Pyber says that in any edge-colouring of a complete graph with r colours, it is possible to cover all the vertices with r vertex-disjoint monochromatic cycles. So far, this conjecture has been proven only for r = 2. In this paper we show that in fact this conjecture is false for all r > 2. In contrast to this, we show that in any edge-colouring of a complete graph with three colours, it is possible to cover all the vertices with three vertex-disjoint monochromatic paths, proving a particular case of a conjecture due to Gy'arf'as. As an intermediate result we show that in any edge-colouring of the complete graph with the colours red and blue, it is possible to cover all the vertices with a red path, and a disjoint blue balanced complete bipartite graph.
Full work available at URL: https://arxiv.org/abs/1205.5492
Recommendations
Coloring of graphs and hypergraphs (05C15) Paths and cycles (05C38) Generalized Ramsey theory (05C55) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- An improved bound for the monochromatic cycle partition number
- Vertex coverings by monochromatic cycles and trees
- Partitioning complete bipartite graphs by monochromatic cycles
- A Ramsey-type problem in directed and bipartite graphs
- Monochromatic cycle partitions of edge-colored graphs
- Covering Two-Edge-Coloured Complete Graphs with Two Disjoint Monochromatic Cycles
- Title not available (Why is that?)
- Partitioning Two-Coloured Complete Graphs into Two Monochromatic Cycles
- Vertex coverings by monochromatic paths and cycles
- Partitioning 3-colored complete graphs into three monochromatic cycles
- Holes in graphs
- Partitioning a graph into a cycle and an anticycle, a proof of Lehel's conjecture
- On the path-complete bipartite Ramsey number
- Title not available (Why is that?)
Cited In (52)
- Partitioning a 2-edge-coloured graph of minimum degree \(2n/3 + o(n)\) into three monochromatic cycles
- Tiling edge-coloured graphs with few monochromatic bounded-degree graphs
- Embedding Graphs into Larger Graphs: Results, Methods, and Problems
- Towards Lehel's conjecture for 4-uniform tight cycles
- Partitioning 2-edge-colored graphs by monochromatic paths and cycles
- Minimum degree conditions for monochromatic cycle partitioning
- Path Ramsey number for random graphs
- Perfect matchings and Hamiltonian cycles in the preferential attachment model
- Vertex covers by monochromatic pieces -- a survey of results and problems
- Monochromatic cycle partitions of graphs with large minimum degree
- Generalizations and strengthenings of Ryser's conjecture
- Improved monochromatic loose cycle partitions in hypergraphs
- Partitioning a graph into a cycle and a sparse graph
- Monochromatic loose-cycle partitions in hypergraphs
- Monochromatic bounded degree subgraph partitions
- Partitioning 3-colored complete graphs into three monochromatic cycles
- Monochromatic cycle partitions of \(2\)-coloured graphs with minimum degree \(3n/4\)
- Monochromatic paths in 2-edge-coloured graphs and hypergraphs
- Ore- and Pósa-type conditions for partitioning 2-edge-coloured graphs into monochromatic cycles
- Large monochromatic components and long monochromatic cycles in random hypergraphs
- Partitioning edge-colored hypergraphs into few monochromatic tight cycles
- On some multicolor Ramsey properties of random graphs
- An alternative proof of the linearity of the size-Ramsey number of paths
- Turán‐type problems for long cycles in random and pseudo‐random graphs
- Monochromatic loose path partitions in \(k\)-uniform hypergraphs
- One-sided coverings of colored complete bipartite graphs
- Partitioning 3-edge-coloured complete bipartite graphs into monochromatic cycles
- Monochromatic cycle partitions in local edge colorings
- Calculating Ramsey numbers by partitioning colored graphs
- Almost partitioning a 3-edge-colored \(K_{n,n}\) into five monochromatic cycles
- The complexity for partitioning graphs by monochromatic trees, cycles and paths
- Local colourings and monochromatic partitions in complete bipartite graphs
- The Rado path decomposition theorem
- Vertex covering with monochromatic pieces of few colours
- Decompositions of edge-coloured infinite complete graphs into monochromatic paths. II
- Partitioning 2-edge-colored Ore-type graphs by monochromatic cycles
- Title not available (Why is that?)
- Partitioning infinite hypergraphs into few monochromatic Berge-paths
- Decompositions of edge-colored infinite complete graphs into monochromatic paths
- Long monochromatic paths and cycles in 2-edge-colored multipartite graphs
- Monochromatic square-cycle and square-path partitions
- Almost partitioning 2-edge-colourings of 3-uniform hypergraphs with two monochromatic tight cycles
- Monochromatic partitions in local edge colorings
- The edge-recoloring cost of monochromatic and properly edge-colored paths and cycles
- Covering graphs by monochromatic trees and Helly-type results for hypergraphs
- Monochromatic cycle power partitions
- Monochromatic cycle partitions of edge-colored graphs
- Size-Ramsey numbers of cycles versus a path
- Partitioning random graphs into monochromatic components
- Problems close to my heart
- Partitioning edge-coloured infinite complete bipartite graphs into monochromatic paths
- Monochromatic cycle partitions in random graphs
This page was built for publication: Partitioning edge-coloured complete graphs into monochromatic cycles and paths
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q402591)
