Nowhere-zero 4-flow in almost Petersen-minor free graphs (Q1011772)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Nowhere-zero 4-flow in almost Petersen-minor free graphs |
scientific article |
Statements
Nowhere-zero 4-flow in almost Petersen-minor free graphs (English)
0 references
9 April 2009
0 references
Unique up to isomorphism, the graph \(\left(P_{10}\right)_{\overline{3}}\) is obtained from a Petersen graph by contracting to a point each of 3 edges in a \(1\)-factor. Addressing a conjecture of \textit{W. T. Tutte} [``On the algebraic theory of graph colorings'', J. Comb. Theory 1, 15--50 (1966; Zbl 0139.41402); ``A correction to: On the algebraic theory of graph colorings'', J. Comb. Theory 3, 102 (1967; Zbl 0152.41202)], the authors prove \textbf{Theorem 1.2.} Let \(G\) be a bridgeless graph. If \(G\) does not have a \(\left(P_{10}\right)_{\overline3}\)-minor, then \(G\) admits a nowhere-zero 4-flow.
0 references
integer flow
0 references
4-flow
0 references
edge-3-colouring
0 references
Petersen minor
0 references
almost Petersen-minor free graphs
0 references