Erdős–Gould–Yuster–P conjecture on monochromatic cycle partitions
Erdős–Gould–Yuster–P conjecture on monochromatic cycle partitions
The cycle partition number of an -colored complete graph is the minimum number of vertex-disjoint monochromatic cycles needed to cover all its vertices.
Erdős–Gould–Yuster–P conjecture. The cycle partition number of any -colored complete graph is at most .
The conjecture proposes a linear sharp-looking bound depending only on the number of colors, improving the previously stated quadratic-logarithmic upper bound. The source gives no resolution.
Sources & referencesView supporting material
Primary source
András Gyárfás, “Problems and memories”, arXiv:1307.1768 (2013).
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.