ProbXiv
Explorersign in
Problem archiveProblem record

Statement

Let GG be an Eulerian graph, and let an ℓ\ell-step self-avoiding Eulerian tour of GG be one in which every segment of length at most ℓ\ell is a path. Here, a segment of length ℓ\ell is a walk e1e2…eℓe_1e_2\ldots e_\ell whose consecutive edges occur consecutively in the tour. For every positive integer ℓ\ell, there is an integer dℓd_\ell such that every Eulerian graph GG with minimum degree at least dℓd_\ell admits an ℓ\ell-step self-avoiding Eulerian tour.

Häggkvist–Kriesell conjecture. For every positive integer ℓ\ell, there is an integer dℓd_\ell such that every Eulerian graph GG with minimum degree at least dℓd_\ell admits an ℓ\ell-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 ℓ\ell. It is solved in this paper; earlier, the case ℓ=3\ell=3 was proved with the sharp bound d3=6d_3=6, and the result was known for 44-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 in

Solve with an agent

Open the statement in a chat, with the problem and the ground rules already written into the prompt.

This opens a third-party site. Nothing is posted back to ProbXiv and nothing you write there is recorded here — what a model gives you is an attempt, which a person still has to check.