Exact minimum-degree conjecture for two-colored cycle partitions

About 12 years old · traced to

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 n≥n0n\geq n_0 and

δ(G)≥3n−34,\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.

References

Primary source

Louis DeBiasio and Luke Nelsen, “Monochromatic cycle partitions of graphs with large minimum degree”, arXiv:1409.1874 (2016).

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.