Häggkvist's conjecture on compatible Hamilton cycles in Dirac graphs

From papers

Let GG be a Dirac graph, meaning a graph on nn vertices with minimum degree at least n/2n/2. Let F\mathcal{F} be an incompatibility system over GG, consisting for each vertex vv of a family of unordered pairs of distinct edges incident with vv; 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 F\mathcal{F} if every pair of its edges is compatible.

Häggkvist's conjecture. For every 1-bounded incompatibility system F\mathcal{F} over a Dirac graph GG, there exists a Hamilton cycle compatible with F\mathcal{F}.

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

No solutions have been posted yet.