Pokrovskiy's bounded-defect monochromatic cycle conjecture

Let rr be a positive integer, and let a complete graph have its edges coloured with rr 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 crc_r, depending only on rr, such that every rr-edge-coloured complete graph has rr vertex-disjoint monochromatic cycles covering all but at most crc_r 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 100rlogr100r\log r 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

Never refreshed

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.