Tutte's 3-flow conjecture and short cycle covers (Q757422)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Tutte's 3-flow conjecture and short cycle covers |
scientific article |
Statements
Tutte's 3-flow conjecture and short cycle covers (English)
0 references
1993
0 references
In this paper we prove: (i) If a graph \(G\) has a nowhere-zero 6-flow \(\phi\) such that \(| E_{odd}(\phi)| \geq \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_{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 \(| E_{odd}(\phi)| \geq \frac{2}{3}| E(G)|\).
0 references
integer flow
0 references
cycle cover
0 references