Häggkvist–Kriesell conjecture on locally self-avoiding Eulerian tours
Statement
Let be an Eulerian graph, and let an -step self-avoiding Eulerian tour of be one in which every segment of length at most is a path. Here, a segment of length is a walk whose consecutive edges occur consecutively in the tour. For every positive integer , there is an integer such that every Eulerian graph with minimum degree at least admits an -step self-avoiding Eulerian tour.
Häggkvist–Kriesell conjecture. For every positive integer , there is an integer such that every Eulerian graph with minimum degree at least admits an -step self-avoiding Eulerian tour.
The conjecture asks for a minimum-degree condition guaranteeing an Eulerian tour with no segment forming a cycle of length at most . It is solved in this paper; earlier, the case was proved with the sharp bound , and the result was known for -edge-connected Eulerian graphs.
Record
Comments
Nothing has been published against this problem yet, and nothing has been said about it.
Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.
Sign inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.