Häggkvist's conjecture on compatible Hamilton cycles in Dirac graphs
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.
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Sources & referencesView supporting material
Primary source
Michael Krivelevich, Choongbum Lee and Benny Sudakov, “Compatible Hamilton cycles in Dirac graphs”, arXiv:1410.1435 (2014).
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.