Exact minimum-degree conjecture for two-colored cycle partitions

From papers

Let GG be a graph on nn vertices whose edges are colored red or blue, and let δ(G)\delta(G) denote its minimum degree. A partition into cycles is a collection of vertex-disjoint monochromatic cycles spanning V(G)V(G).

Exact cycle-partition conjecture. There exists an integer n0n_0 such that, whenever nn0n\geq n_0 and

δ(G)3n34,\delta(G)\geq\frac{3n-3}{4},

GG 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

No solutions have been posted yet.