Tutte's 3-flow conjecture and short cycle covers (Q757422): Difference between revisions
From MaRDI portal
Removed claim: author (P16): Item:Q801081 |
Set OpenAlex properties. |
||
(4 intermediate revisions by 4 users not shown) | |||
Property / author | |||
Property / author: Geng-Hua Fan / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
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