Snarks with Resistance $n$ and Flow Resistance $2n$

  • Imran Allie
  • Edita Máčajová
  • Martin Škoviera

Abstract

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$. Fiol et al. [Electron. J. Combin. 25 (2018), $\#$P4.54] made a conjecture that $r_f(G) \leq 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 \geq 3$, with resistance $n$ and flow resistance $2n$. For $n\ge 5$ these graphs are nontrivial snarks.

Published
2022-03-11
Article Number
P1.44