Partitioning edge-coloured complete graphs into monochromatic cycles and paths
From MaRDI portal
(Redirected from Publication:402591)
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.
Recommendations
Cites work
- scientific article; zbMATH DE number 1185305 (Why is no real title available?)
- scientific article; zbMATH DE number 15152 (Why is no real title available?)
- scientific article; zbMATH DE number 1432797 (Why is no real title available?)
- scientific article; zbMATH DE number 3262254 (Why is no real title available?)
- A Ramsey-type problem in directed and bipartite graphs
- An improved bound for the monochromatic cycle partition number
- Covering Two-Edge-Coloured Complete Graphs with Two Disjoint Monochromatic Cycles
- Holes in graphs
- Monochromatic cycle partitions of edge-colored graphs
- On the path-complete bipartite Ramsey number
- Partitioning 3-colored complete graphs into three monochromatic cycles
- 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 complete bipartite graphs by monochromatic cycles
- Vertex coverings by monochromatic cycles and trees
- Vertex coverings by monochromatic paths and cycles
Cited in
(53)- Partitioning Two-Coloured Complete Graphs into Two Monochromatic Cycles
- Partitioning 2-edge-colored graphs by monochromatic paths and cycles
- Towards Lehel's conjecture for 4-uniform tight cycles
- Embedding Graphs into Larger Graphs: Results, Methods, and Problems
- Minimum degree conditions for monochromatic cycle partitioning
- Perfect matchings and Hamiltonian cycles in the preferential attachment model
- Path Ramsey number for random graphs
- 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
- Monochromatic loose-cycle partitions in hypergraphs
- Generalizations and strengthenings of Ryser's conjecture
- Partitioning a graph into a cycle and a sparse graph
- 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
- Large monochromatic components and long monochromatic cycles in random hypergraphs
- Ore- and Pósa-type conditions for partitioning 2-edge-coloured graphs into monochromatic cycles
- 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
- Partitioning a 2-edge-coloured graph of minimum degree \(2n/3 + o(n)\) into three monochromatic cycles
- Partitioning 3-edge-coloured complete bipartite graphs into monochromatic cycles
- Tiling edge-coloured graphs with few monochromatic bounded-degree graphs
- Monochromatic loose path partitions in k-uniform hypergraphs
- One-sided coverings of colored complete bipartite graphs
- 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
- The Rado path decomposition theorem
- Local colourings and monochromatic partitions in complete bipartite graphs
- 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
- scientific article; zbMATH DE number 4137782 (Why is no real title available?)
- 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
- Size-Ramsey numbers of cycles versus a path
- Monochromatic cycle partitions of edge-colored graphs
- 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)
