Exact minimum-degree conjecture for two-colored cycle partitions
Exact minimum-degree conjecture for two-colored cycle partitions
Let be a graph on vertices whose edges are colored red or blue, and let denote its minimum degree. A partition into cycles is a collection of vertex-disjoint monochromatic cycles spanning .
Exact cycle-partition conjecture. There exists an integer such that, whenever and
has a partition into a red cycle and a blue cycle.
The examples preceding this statement show that the threshold is sharp up to the strictness and rounding at the boundary. The source does not report a resolution of this exact asymptotic formulation.
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
Louis DeBiasio and Luke Nelsen, “Monochromatic cycle partitions of graphs with large minimum degree”, arXiv:1409.1874 (2016).
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.