Tight cycle-partition conjecture for dense edge-coloured graphs
Tight cycle-partition conjecture for dense edge-coloured graphs
For and , let
where consists of the -vertex -edge-coloured graphs with , and is the smallest number of vertex-disjoint monochromatic cycles partitioning . Tight cycle-partition conjecture. There exists such that, for all and ,
The conjecture would improve the paper's upper bound to the matching order suggested by the lower bound. It is known for , but remains open in general.
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Sources & referencesView supporting material
Primary source
Francesco Di Braccio and Viresh Patel, “Monochromatic cycle partitions of r-edge-coloured graphs with high minimum degree”, arXiv:2601.22117 (2026).
Additional references
3 papers in this index state this conjecture (2015–2026). The statement above is taken from the most recent of them; the others are arXiv:2008.00926, arXiv:1509.05539.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.