Circuit Decompositions of Eulerian Graphs

Let G be an eulerian graph. For each vertex v∈V(G), let P(v) be a partition of the edges incident with v and set P=∪v∈V(G) P(v), called a forbidden system of G. We say that P is admissible if |P∩T|⩽12 |T| for every P∈P and every edge cut T of G. H. Fleischner and A. Frank (1990, J. Combin. Theory Ser. B50, 245–253) proved that if G is planar and P is any admissible forbidden system of G, then G has a circuit decomposition F such that |C∩P|⩽1 for every C∈F and every P∈P. We generalize this result to all eulerian graphs that do not contain K5 as a minor. As a consequence, a conjecture of Sabidussi is settled for graphs that do not contain K5 as a minor. Also, as a byproduct, our proof provides a different approach to the circuit cover theorem of B. Alspach, L. A. Goddyn, and C.-Q. Zhang (1994, Trans. Amer. Math. Soc.344, No. 1, 131–154).