Aharoni's transversal Dirac conjecture
Let be a collection of graphs with common vertex set of size . Define , where is the minimum degree of . A transversal Hamilton cycle is a Hamilton cycle whose edges can be assigned distinct representatives from the graphs , with the edge assigned to belonging to . Aharoni's transversal Dirac conjecture. If
then 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
Status
- Solved: Felix Joos and Jaehoon Kim. On a rainbow version of Dirac's theorem (Bulletin of the London Mathematical Society, 2020) https://londmathsoc.onlinelibrary.wiley.com/doi/10.1112/blms.12343
Source: Yangyang Cheng, Wanting Sun, Guanghui Wang and Lan Wei, “Transversal Hamilton paths and cycles”, arXiv:2406.13998 (2024).
Progress summary
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.