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
    0 references
    0 references
    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

    Identifiers