Tutte's 3-flow conjecture and short cycle covers (Q757422): Difference between revisions
From MaRDI portal
Set profile property. |
Set OpenAlex properties. |
||
(2 intermediate revisions by 2 users not shown) | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1006/jctb.1993.1004 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W1986722082 / rank | |||
Normal rank |
Latest revision as of 19:02, 19 March 2024
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