Häggkvist's transversal cycle-factor conjecture for blow-ups of cycles

About 5 years old · traced to

Let CkC_k be the cycle on kk vertices, and let the nn-blow-up of CkC_k be the graph with vertex parts V1,…,VkV_1,\dots,V_k, each of size nn, where consecutive parts are joined according to the edges of CkC_k. For a spanning subgraph GG of this blow-up, write δ∗(G)\delta^*(G) for its minimum degree between consecutive vertex parts. A transversal CkC_k-factor is a collection of nn vertex-disjoint copies of CkC_k, each containing one vertex from every part.

Häggkvist's conjecture. For every k≥3k\geq 3, if

δ∗(G)≥(1+1k)n2+1,\delta^*(G)\geq \left(1+\frac{1}{k}\right)\frac{n}{2}+1,

then GG has a transversal CkC_k-factor.

The conjecture is tight when k=3k=3, while the example described in the source shows that for k≥4k\geq4 the degree threshold cannot be decreased by more than 11.

References

Primary source

Beka Ergemlidze and Theodore Molla, “Transversal C_k-factors in subgraphs of the balanced blow-up of C_k”, arXiv:2103.09745 (2021).

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.