Snarks with resistance \(n\) and flow resistance \(2n\) (Q2121784)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Snarks with resistance \(n\) and flow resistance \(2n\)
scientific article

    Statements

    Snarks with resistance \(n\) and flow resistance \(2n\) (English)
    0 references
    0 references
    0 references
    0 references
    4 April 2022
    0 references
    Summary: We examine the relationship between two measures of uncolourability of cubic graphs -- their resistance and flow resistance. The resistance of a cubic graph \(G\), denoted by \(r(G)\), is the minimum number of edges whose removal results in a 3-edge-colourable graph. The flow resistance of \(G\), denoted by \(r_f(G)\), is the minimum number of zeroes in a 4-flow on \(G\). \textit{M. A. Fiol} et al. [ibid. 25, No. 4, Research Paper P4.54, 35 p. (2018; Zbl 1409.05086)] made a conjecture that \(r_f(G) \leqslant r(G)\) for every cubic graph \(G\). We disprove this conjecture by presenting a family of cubic graphs \(G_n\) of order \(34n\), where \(n \geqslant 3\), with resistance \(n\) and flow resistance \(2n\). For \(n\geqslant 5\) these graphs are nontrivial snarks.
    0 references
    resistance of a cubic graph
    0 references
    Tait coloring
    0 references
    snark
    0 references
    Boole coloring
    0 references
    Berge's conjecture
    0 references
    Tutte's 5-flow conjecture
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references