SAMS Subject Classification Number: 06

Vizing’s theorem categorises graphs into two classes: those which are \(\Delta(G)\)-edge-colourable (class one, colourable), and those which are not (class two, uncolourable). By \(\Delta(G)\)-edge-colourable we mean graphs whose edges can be coloured with \(\Delta(G)\) colours such that no two adjacent edges have the same colour. Cubic class two graphs are of particular interest, for the reason that many major open conjectures in graph theory are reducible to just to the consideration of these graphs. In contemporary times, so-called measures of uncolourability have been studied in order to develop insights into cubic class two graphs. Let \(G\) be cubic. Resistance, \(r(G)\), is defined as the minimum number of edges which can be removed from \(G\) in order to render a class one graph, an intuitive measure of uncolourability. Flow resistance, \(r_f(G)\), defined as the minimum number of zero edges in a 4-flow of \(G\), is another measure of uncolourability, although less intuitive. (\(r(G)=r_f(G)=0\) if and only if \(G\) is colourable). It has been conjectured, with good reason, that \(r(G) \geq r_f(G)\) for all cubic \(G\) [1]. In this talk, we explain the motivation for this conjecture, and prove a surprising result which disproves it. We prove that the ratio of flow-resistance to resistance can in fact be arbitrarily large.

[1] M. A. Fiol, G. Mazzuoccolo and E. Steffen, Measures of edge-uncolourability of cubic graphs, Electron. J. Combin. 25 (2018), \(\#\)P4.54.