Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
5777106 | Electronic Notes in Discrete Mathematics | 2017 | 5 Pages |
Let G be an eulerian graph. For each vertex vâV(G), let T(v) be a non-empty subset of a partition of the edges incident with v into 2-subsets and set T=âªvâV(G)T(v), called a transition system of G. A transition system T of G is admissible if Tâ©F|â¤12|F| for every TâT and every edge cut F of G. A cycle decomposition C of G is called a compatible cycle decomposition (CCD for short) of (G, T) if |E(C)â©T|â¤1 for every cycle CâC and every TâT. H. Fleischner proved that if G is planar, then for every admissible transition system T of G, (G, T) has a CCD. G. Fan and C.-Q. Zhang (2000, J. Combin. Theory Ser. B 78, 1-23) showed that this result is also true for K5-minor-free graphs. We generalize this result to all eulerian graphs that do not contain a special type of K5-minor which is called a bad K5-minor. To this purpose, we characterise the 4âregular “hereditary” bad K5-minor-free graphs (G, T) in which every CCD of (G, T) is a pair of hamiltonian cycles.