FULKERSON CONJECTURE AND CIRCUIT COVERS

It was conjectured by Fulkerson that the edge-set of any bridgeless gr aph can be covered by six cycles (union of circuits) such that each ed ge is in exactly four cycles. We prove that if Fulkerson's conjecture is true, then the edge-set of every bridgeless graph G can be covered by three cycles whose total length is at most 22/15\E(G)\. We also pro ve that there are infinitely many bridgeless graphs G whose edge-set c annot be covered by three cycles of total length less than 22/15\E(G)\ . (C) 1994 Academic Press, Inc.