Compatible Euler-tours
If G is an undirected graph with even degrees then call two closed Eulerian walks compatible if no pair of incident edges occurs consecutively in both. Is it true that the maximum number of pairwise compatible Euler walks in an Eulerian graph of minimum degree 2d is either 2d-2 or 2d-1?
Remarks
This conjecture appeared in [1]. Note that the upper bound 2d-1 is easy. It was motivated by an old result of Kotzig [2] which implies it is true when d=2, and Jackson [3] gave a good characterization of connected 4-regular graphs that have 3 pairwise compatible Euler walks. Bouchet [4] gave a more general, defect version of this theorem.
Kotzig had previously conjectured that the upper bound is attained by [math]K_{2d+1}[/math], and this has been verified for arbitrary d in [1]. In [5] the conjecture was also verified when d=3. For more information and references, see [6].
Related conjectures
References
- ↑ 1.0 1.1 B. Jackson, Compatible Euler tours for transition systems in Eulerian graphs, Discrete Math., 66 (1987) 127-131. DOI link.
- ↑ A. Kotzig, Moves without forbidden transitions in a graph, EUDML link
- ↑ B. Jackson, A characterisation of graphs having three pairwise compatible Euler tours, DOI link
- ↑ A. Bouchet, Compatible Euler Tours and Supplementary Eulerian Vectors, DOI link
- ↑ B. Jackson, N. Wormald, Cycles containing matchings and pairwise compatible Euler tours, J. Graph Theory 14 (1990), 127-138. DOI link.
- ↑ B. Jackson, On circuit covers, circuit decompositions and Euler tours of graphs, in Surveys in Combinatorics, 1993, K Walker ed., Cambridge University Press, (1993) 191-210. Google Books link.
