Cycle covers (III) Compatible circuit decomposition and K-5-transition minor

摘要

Let G be a 2-connected eulerian graph. For each vertex v is an element of V(G), let T(v) be the set of edge-disjoint edge-pairs of E(v), and, T = U-v is an element of V(G) T(v). A circuit decomposition C of G is compatible with 'T if vertical bar E(C) boolean AND P vertical bar <= 1 for every member C is an element of C and every P is an element of T. Fleischner (1990's) wondered implicitly whether if (G, T) does not have a compatible circuit decomposition then (G, T) must have an undecomposable K-5-transition-minor or its generalized transition-minor. This long-standing open problem was partially verified for various graph-minor-free families of graphs, for example, it was solved by Fleischner for planar graphs (Fleischner (1980) [7]) and solved by Fan and Zhang for K-5-minor-free graphs (Fan and Zhang (2000) [6]). This transition-minor-free conjecture is now completely solved in this paper. And, as a by-product and a necessary stepping-stone, we characterize the structure of sup-undecomposable K-5-minor-free graphs (G, in which every compatible circuit decomposition consists of a pair of Hamiltonian circuits. This result plays an important role in the proof of the main theorem and also generalizes an earlier result by Lai and Zhang (Lai and Zhang (2001) [13]). (C) 2018 Elsevier Inc. All rights reserved.