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