Häggkvist's conjecture on compatible Hamilton cycles in Dirac graphs
Let be a Dirac graph, meaning a graph on vertices with minimum degree at least . Let be an incompatibility system over , consisting for each vertex of a family of unordered pairs of distinct edges incident with ; edges in one of these pairs are incompatible. The system is 1-bounded if every edge incident with any vertex is incompatible with at most one other edge at that vertex. A Hamilton cycle is compatible with if every pair of its edges is compatible.
Häggkvist's conjecture. For every 1-bounded incompatibility system over a Dirac graph , there exists a Hamilton cycle compatible with .
The paper presents this as a conjecture of Häggkvist from 1988 motivating its study. The supplied text gives no resolution status, so the conjecture is recorded as open.
References
- Michael Krivelevich, Choongbum Lee and Benny Sudakov, “Compatible Hamilton cycles in Dirac graphs”, arXiv:1410.1435 (2014).
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.