Fulkerson's conjecture and circuit covers
type: Item
instance of: scholarly article
title: Fulkerson's conjecture and circuit covers
zbMATH Open document ID: 0811.05053
published in: Journal of Combinatorial Theory. Series B
publication date: 1995-05-03T00:00:00Z
review text: Fulkerson's famous conjecture states that every bridgeless cubic graph has six perfect matchings such that each edge is in exactly two of the matchings. An algebraic cycle is a (possibly empty) graph where all vertices have even degree. In other words, it is the edge-disjoint union of ordinary cycles. A 3-cycle cover of a graph \(G\) consists of three subgraphs \(G_ 1\), \(G_ 2\), \(G_ 3\) of \(G\) that are algebraic cycles, and where every edge of \(G\) lies in some \(G_ i\). Since algebraic cycles can not contain bridges, every such \(G\) must be bridgeless. Conversely, \textit{F. Jaeger} showed that every bridgeless graph has some 3-cycle cover [J. Comb. Theory, Ser. B 26, 205-216 (1979; Zbl 0422.05028)]. In the present paper it is proven that, provided Fulkerson's conjecture were true, every bridgeless graph \(G = (V,E)\) had some 3-cycle cover \(G_ 1\), \(G_ 2\), \(G_ 3\) such that \(| E(G_ 1)| + | E(G_ 2)| + | E(G_ 3)| \leq {22 \over 15} | E(G)|\). This would improve the bound \({5 \over 3} | E(G) |\) of \textit{J. C. Bermond}, \textit{B. Jackson}, and \textit{F. Jaeger} [J. Comb. Theory, Ser. B 35, 297-308 (1983; Zbl 0559.05037)], which however is not dependent on Fulkerson's conjecture. Furthermore the authors present examples that the bound \({22 \over 15} | E(G)|\) is sharp.
reviewed by: Erich Prisner
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 05C38
zbMATH DE Number: 599870
zbMATH Keywords: circuit covers
zbMATH Keywords: cycle cover
zbMATH Keywords: perfect matchings
zbMATH Keywords: algebraic cycle
zbMATH Keywords: bridges
zbMATH Keywords: Fulkerson's conjecture
zbMATH Keywords: bridgeless graph
zbMATH Keywords: bound
author: Genghua Fan
author: André Raspaud
MaRDI profile type: Publication
full work available at URL: jctb.1994.1039
OpenAlex ID: W2013356944
DOI: 10.1006/JCTB.1994.1039
description: scientific article; zbMATH DE number 599870