Hwang's even-cycle packing conjecture

At least 10 years old · documented by

Let GG be a graph, and let k≥3k\geq 3 and even r≥6r\geq 6 be integers.

Hwang's even-cycle packing conjecture. If GG has at least rkrk vertices and minimum degree at least

r2k,\tfrac{r}{2}k,

then GG contains kk disjoint cycles, each containing at least rr vertices, unless kk is odd and

rk+1≤∣V(G)∣≤rk+r−2.rk+1\leq |V(G)|\leq rk+r-2.

The exceptional range is explained in the source by disjoint unions of two cliques, which can meet the degree requirement without containing the required cycle packing. The conjecture is presented as open.

References

Primary source

Daniel J. Harvey and David R. Wood, “Cycles of given size in a dense graph”, arXiv:1502.03549 (2015).

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.