Sárközy's cycle partition conjecture for edge-colored graphs

Let GG be a tt-colored graph, and let α(G)\alpha(G) denote its independence number. Let the cycle partition number be the minimum number of vertex-disjoint monochromatic cycles covering V(G)V(G). Sárközy's conjecture. The cycle partition number of any tt-colored graph GG is

tα(G).t\alpha(G).

The statement is known for t=1t=1 and is best possible for t=2t=2, but Pokrovskiy's example shows that it is false for every t3t\geq3.

Sources & referencesView supporting material

Primary 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).

Additional 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.

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.