Tutte′s 3-Flow Conjecture and Short Cycle Covers

✍ Scribed by G.H. Fan

• Publisher: Elsevier Science
• Year: 1993
• Tongue: English
• Weight: 285 KB
• Volume: 57
• Category: Article
• ISSN: 0095-8956
• DOI: 10.1006/jctb.1993.1004

✦ Synopsis

In this paper we prove: (i) If a graph (G) has a nowhere-zero 6 -llow (\phi) such that (\left|E_{\text {odd }}(\phi)\right| \geqslant \frac{2}{3}|E(G)|), then (G) has a cycle cover in which the sum of the lengths of the cycles in the cycle cover is at most (\frac{44}{27}|E(G)|), where (E_{\text {odd }}(\phi)={e \in E(G): \phi(e)) is odd }; (ii) if Tutte's 3-Flow Conjecture is true, then every bridgeless graph (G) has a nowhere-zero 6-flow (\phi) such that (\left|E_{\text {odd }}(\phi)\right| \geqslant \frac{2}{3}|E(G)| . \quad) । 1993 Academic Press. Inc.