An equivalent statement of the circuit double cover conjecture is that every bridgeless graph G has a circuit cover such that each vertex v of G is contained in at most d(v) circuits of the cover, where d(v) is the degree of v. Pyber conjectured that every bridgeless graph G has a circuit cover such that every vertex of G is contained in at most Delta(G) circuits of the cover, where Delta(G) is the maximum degree of G. This paper affirms Pyber's conjecture by establishing an intermediate result, namely that every bridgeless graph G has a circuit cover such that each vertex v of G is contained in at most d(v) circuits of the cover if d(v) greater than or equal to 3 and in at most three circuits of the cover if d(v) = 2. Our proofs rely on results on integer flows. (C) 1995 Academic Press, Inc. [References: 10]
展开▼
