Decomposing an eulerian graph into cycles with no two consecutives edges on a prescribed eulerian tour.

Importance: Medium ✭✭
Author(s): Sabidussi, Gert
Recomm. for undergrads: no
Posted by: fhavet
on: March 4th, 2013

\begin{conjecture} Let $G$ be an eulerian graph of minimum degree $4$, and let $W$ be an eulerian tour of $G$. Then $G$ admits a decomposition into cycles none of which contains two consecutive edges of $W$. \end{conjecture}

Kotzig proved the converse statement: \begin{theorem} Let $G$ be an eulerian graph of minimum degree $4$ and let $(C_1, \dots , C_p)$ be a decomposition into cycles of $G$. Then $G$ admits an eulerian tour such that none of the $C_i$, $1\leq i\leq p$, contains two consecutive edges of $W$. \end{theorem}

For more details on eulerian graphs, see [F].

% You may use many features of TeX, such as % arbitrary math (between $...$ and $$...$$) % \begin{theorem}...\end{theorem} environment, also works for question, problem, conjecture, ... % % Our special features: % Links to wikipedia: \Def {mathematics} or \Def[coloring]{Graph_coloring} % General web links: \href [The On-Line Encyclopedia of Integer Sequences]{}


*[F] H. Fleischner. Eulerian Graphs and Related Topics. Part 1. Vol. 1. Annals of Discrete Mathematics, Vol. 45, (1990) North-Holland, Amsterdam.

% Example: %*[B] Claude Berge, Farbung von Graphen, deren samtliche bzw. deren ungerade Kreise starr sind, Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg Math.-Natur. Reihe 10 (1961), 114. % %[CRS] Maria Chudnovsky, Neil Robertson, Paul Seymour, Robin Thomas: \arxiv[The strong perfect graph theorem]{math.CO/0212070}, % Ann. of Math. (2) 164 (2006), no. 1, 51--229. \MRhref{MR2233847} % % (Put an empty line between individual entries)

* indicates original appearance(s) of problem.