Pokrovskiy's bounded-defect monochromatic cycle conjecture
Pokrovskiy's bounded-defect monochromatic cycle conjecture
Let be a positive integer, and let a complete graph have its edges coloured with colours. A collection of vertex-disjoint monochromatic cycles consists of cycles with pairwise disjoint vertex sets, each cycle having edges of a single colour. Pokrovskiy's conjecture. There is a constant , depending only on , such that every -edge-coloured complete graph has vertex-disjoint monochromatic cycles covering all but at most vertices. This is presented as a widely open alternative to the refuted Erdős–Gyárfás–Pyber conjecture; the best general result cited in the source uses at most monochromatic cycles for sufficiently large graphs.
Sources & referencesView supporting material
Primary source
Sebastián Bustamante, Jan Corsten, Nóra Frankl, Alexey Pokrovskiy and Jozef Skokan, “Partitioning edge-coloured hypergraphs into few monochromatic tight cycles”, arXiv:1903.04471 (2020).
Additional references
3 papers in this index state this conjecture (2015–2019). The statement above is taken from the most recent of them; the others are arXiv:1607.03348, arXiv:1509.05539.
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
Sign in to submit a solution.
No solutions have been posted yet.