Aharoni's transversal Dirac conjecture

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):1in}\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.

Sources & referencesView supporting material

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.