Aharoni's transversal Dirac conjecture

About 2 years old · traced to

Let G={G1,…,Gn}\mathcal{G} = \{G_1, \ldots, G_n\} be a collection of graphs with common vertex set VV of size nn. Define δ(G)=min⁡{δ(Gi):1≤i≤n}\delta(\mathcal{G})=\min\{\delta(G_i):1\leq i\leq n\}, where δ(Gi)\delta(G_i) is the minimum degree of GiG_i. A transversal Hamilton cycle is a Hamilton cycle whose edges can be assigned distinct representatives from the graphs G1,…,GnG_1,\ldots,G_n, with the edge assigned to GiG_i belonging to GiG_i. Aharoni's transversal Dirac conjecture. If

δ(G)≥n2,\delta(\mathcal{G})\geq \frac{n}{2},

then G\mathcal{G} contains a transversal Hamilton cycle. This conjecture extends Dirac's Hamilton-cycle theorem to graph collections; it was solved asymptotically by Cheng, Wang and Zhao and completely confirmed by Joos and Kim.

References

Primary source

Yangyang Cheng, Wanting Sun, Guanghui Wang and Lan Wei, “Transversal Hamilton paths and cycles”, arXiv:2406.13998 (2024).

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.