Resistance in regular class two graphs

Allie, Imran  ; Arenstein, Jordan

Discussiones Mathematicae. Graph Theory, Tome 44 (2024) no. 2, pp. 727-736

Résumé

A well-known theorem of Vizing separates graphs into two classes: those which admit proper Δ-edge-colourings, known as class one graphs; and those which do not, known as class two graphs. Class two graphs do admit proper (Δ+1)-edge-colourings. In the context of snarks (class two cubic graphs), there has recently been much focus on parameters which are said to measure how far the snark is from being 3-edge-colourable, and there are thus many well-known lemmas and results which are widely used in the study of snarks. These parameters, or so-called measurements of uncolourability, have thus far evaded consideration in the general case of k-regular class two graphs for k gt; 3. Two such measures are the resistance and vertex resistance of a graph. For a graph G, the (vertex) resistance of G, denoted as (r_v(G)) r(G), is defined as the minimum number of (vertices) edges which need to be removed from G in order to render it class one. In this paper, we generalise some of the well-known lemmas and results to the k-regular case. For the main result of this paper, we generalise the known fact that r(G)=r_v(G) if G is a snark by proving the following bounds for k-regular G: r_v(G) ≤ r(G) ≤⌊k/2⌋ r_v(G). Moreover, we show that both bounds are best possible for any even k.

Détail

Keywords: class two graphs, resistance, vertex resistance