2016/11/22 by Le, Tien-Nam
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1611.07486
It was independently conjectured by Häggkvist in 1989 and Kriesell in 2011 that given a positive integer ℓ, every simple eulerian graph with high minimum degree (depending on ℓ) admits an eulerian tour such that every segment of length at most ℓ of the tour is a path. Bensmail, Harutyunyan, Le and Thomassé recently verified the conjecture for 4-edge-connected eulerian graphs. Building on that proof, we prove here the full statement of the conjecture. This implies a variant of the path case of Barát-Thomassen conjecture that any simple eulerian graph with high minimum degree can be decomposed into paths of fixed length and possibly an additional shorter path.