Article in volume
Authors:
Title:
Resistance in regular class two graphs
PDFSource:
Discussiones Mathematicae Graph Theory 44(2) (2024) 727-736
Received: 2022-02-25 , Revised: 2022-07-11 , Accepted: 2022-07-11 , Available online: 2022-08-26 , https://doi.org/10.7151/dmgt.2467
Abstract:
A well-known theorem of Vizing separates graphs into two classes: those which
admit proper $\Delta$-edge-colourings, known as class one graphs; and those
which do not, known as class two graphs. Class two graphs do admit proper
$(\Delta+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 > 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) \leq r(G)
\leq \lfloor \frac{k}{2} \rfloor r_v(G)$. Moreover, we show that both bounds
are best possible for any even $k$.
Keywords:
class two graphs, resistance, vertex resistance
References:
- 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 - I. Allie, A note on reducing resistance in snarks, Quaest. Math.(2022), in press.
https://doi.org/10.2989/16073606.2022.2053605 - I. Allie, E. Máčajova and M. Škoviera, Snarks with resistance n and flow resistance $2$n, Electron. J. Combin. 29(1) (2022) #P1.44.
https://doi.org/10.37236/10633 - 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 - E.J. Pegg, S. Wagon and E. Weisstein, Class $2$ graph (Wolfram MathWorld, 2022).
https://mathworld.wolfram.com/Class2Graph.html - 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 - 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 - 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 - J. Karábaš, E. Máčajova, R. Nedela and M. Škoviera, Girth, oddness and colouring defect of snarks (2021).
arXiv: 2106.12205v3 - M. Kochol, Three measures of edge-uncolorability, Discrete Math. 311 (2011) 106–108.
https://doi.org/10.1016/j.disc.2010.10.001 - 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 - 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 - E. Steffen, Measurements of edge-uncolorability, Discrete Math. 280 (2004) 191–214.
https://doi.org/10.1016/j.disc.2003.05.005 - E. Steffen, Classifications and characterizations of snarks, Discrete Math. 188 (1998) 183–203.
https://doi.org/10.1016/S0012-365X(97)00255-0 - E. Steffen, $1$-factor and cycle covers of cubic graphs, J. Graph Theory 78 (2015) 195–206.
https://doi.org/10.1002/jgt.21798 - V. Vizing, On an estimate of the chromatic class of a p-graph, Diskret. Analiz. 3 (1964) 9–17, in Russian.
- V. Vizing, The chromatic class of a multigraph, Cybernet. Systems Anal. 1 (1965) 32–41.
https://doi.org/10.1007/BF01885700
Close