Sárközy's cycle partition conjecture for edge-colored graphs
Let be a -colored graph, and let denote its independence number. Let the cycle partition number be the minimum number of vertex-disjoint monochromatic cycles covering . Sárközy's conjecture. The cycle partition number of any -colored graph is
The statement is known for and is best possible for , but Pokrovskiy's example shows that it is false for every .
References
2 papers in this index state this conjecture (2015). The statement above is taken from the most recent of them; the others are arXiv:1509.05539.
Status
- Refuted: Alexey Pokrovskiy. Partitioning edge-coloured complete graphs into monochromatic cycles and paths (arXiv, 2012) https://arxiv.org/abs/1205.5492
Source: Jozsef Balogh, Janos Barat, Daniel Gerbner, Andras Gyarfas and GAbor N. Sarkozy, “Partitioning 2-edge-colored graphs by monochromatic paths and cycles”, arXiv:1509.05544 (2015).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
No solutions have been posted yet.