Pósa-type degree-sequence conjecture for monochromatic cycle partitions

About 4 years old · traced to

Let d1≤⋯≤dnd_1\leq\dots\leq d_n be the degree sequence of a graph GG. The degree-sequence conjecture. There is a function ff such that, for every β>0\beta>0, every integer r≥2r\geq 2, and all sufficiently large nn, if

di≥i+βnd_i\geq i+\beta n

for every i≤n/2i\leq n/2, then every rr-edge-colouring of GG admits a partition of V(G)V(G) into at most f(r)f(r) monochromatic cycles. This conjecture extends Pósa-type Hamiltonicity conditions to coloured cycle partitions; an approximate solution is known for r=2r=2, but the general assertion remains open.

References

Primary source

Peter Allen, Julia Böttcher, Richard Lang, Jozef Skokan and Maya Stein, “Partitioning a 2-edge-coloured graph of minimum degree 2n/3 + o(n) into three monochromatic cycles”, arXiv:2204.00496 (2022).

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.