Decomposing Eulerian Graphs

Abstract

Heinrich et al. [4] characterized those simple eulerian graphs with no Petersen-minor which admit a triangle-free cycle decomposition, a TFCD. If one permits Petersen minors then no such characterization is known even for $E(4,2)$, the set of all the eulerian graphs of maximum degree 4. Let $EM(4,2)\subset E(4,2)$ be the set of all graphs $H$ such that all triangles of $H$ are vertex disjoint, and each triangle contains a degree 2 vertex in $H$. In the paper it is shown that to each $G\in E(4,2)$ there exists a finite subset $S\subset EM(4,2)$ so that $G$ admits a TFCD if and only if some $H\in S$ admits a TFCD. Further, some sufficient conditions for a graph $G\in E(4,2)$ to possess a TFCD are given.