Erdős–Gould–Yuster–P conjecture on monochromatic cycle partitions

The cycle partition number of an rr-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 rr-colored complete graph is at most rr.

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

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.