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

Bibliographie

[1] I. Allie, Oddness to resistance ratios in cubic graphs, Discrete Math. 342 (2019) 387–392. https://doi.org/10.1016/j.disc.2018.10.014

[2] I. Allie, A note on reducing resistance in snarks, Quaest. Math.(2022), in press. https://doi.org/10.2989/16073606.2022.2053605

[3] I. Allie, E. Máčajova and M. Škoviera, Snarks with resistance n and flow resistance 2n, Electron. J. Combin. 29(1) (2022) #P1.44. https://doi.org/10.37236/10633

[4] G. Brinkmann and E. Steffen, Chromatic-index-critical graphs of orders 11 and 12, European J. Combin. 19 (1998) 889–900. https://doi.org/10.1006/eujc.1998.0254

[5] E.J. Pegg, S. Wagon and E. Weisstein, Class 2 graph (Wolfram MathWorld, 2022). https://mathworld.wolfram.com/Class2Graph.html

[6] M.A. Fiol, G. Mazzuoccolo and E. Steffen, Measures of edge-uncolourability of cubic graphs, Electron. J. Combin. 25(4) (2018) #P4.54. https://doi.org/10.37236/6848

[7] H. Izbicki, Zulässige Kantenfärbungen von pseudo-regulären Graphen 3. Grades mit der Kantenfarbenzahl 3, Monatsh. Math. 66 (1962) 424–430. https://doi.org/10.1007/BF01298238

[8] L. Jin and E. Steffen, Petersen cores and the oddness of cubic graphs, J. Graph Theory 84 (2017) 109–120. https://doi.org/10.1002/jgt.22014

[9] J. Karábaš, E. Máčajova, R. Nedela and M. Škoviera, Girth, oddness and colouring defect of snarks (2021). arXiv: 2106.12205v3

[10] M. Kochol, Three measures of edge-uncolorability, Discrete Math. 311 (2011) 106–108. https://doi.org/10.1016/j.disc.2010.10.001

[11] R. Lukot'ka and J. Mazák, Weak oddness as an approximation of oddness and resistance in cubic graphs, Discrete Math. 244 (2018) 223–226. https://doi.org/10.1016/j.dam.2018.02.021

[12] D. Mattiolo and E. Steffen, Edge colorings and circular flows on regular graphs, J. Graph Theory 99 (2022) 399–413. https://doi.org/10.1002/jgt.22746

[13] E. Steffen, Measurements of edge-uncolorability, Discrete Math. 280 (2004) 191–214. https://doi.org/10.1016/j.disc.2003.05.005

[14] E. Steffen, Classifications and characterizations of snarks, Discrete Math. 188 (1998) 183–203. https://doi.org/10.1016/S0012-365X(97)00255-0

[15] E. Steffen, 1-factor and cycle covers of cubic graphs, J. Graph Theory 78 (2015) 195–206. https://doi.org/10.1002/jgt.21798

[16] V. Vizing, On an estimate of the chromatic class of a p-graph, Diskret. Analiz. 3 (1964) 9–17, in Russian.

[17] V. Vizing, The chromatic class of a multigraph, Cybernet. Systems Anal. 1 (1965) 32–41. https://doi.org/10.1007/BF01885700