Geodesic
Coverings of Cubic Graphs and 3-Edge Colorability
Discussiones Mathematicae. Graph Theory, Tome 41 (2021) no. 1, pp. 311-334.

Voir la notice de l'article provenant de la source Library of Science

Let h:G̃→G be a finite covering of 2-connected cubic (multi)graphs where G is 3-edge uncolorable. In this paper, we describe conditions under which G̃ is 3-edge uncolorable. As particular cases, we have constructed regular and irregular 5-fold coverings f:G̃→G of uncolorable cyclically 4-edge connected cubic graphs and an irregular 5-fold covering g:H̃→H of uncolorable cyclically 6-edge connected cubic graphs. In [13], Steffen introduced the resistance of a subcubic graph, a characteristic that measures how far is this graph from being 3-edge colorable. In this paper, we also study the relation between the resistance of the base cubic graph and the covering cubic graph.
Keywords: uncolorable cubic graph, covering of graphs, voltage permutation graph, resistance, nowhere-zero 4-flow 
@article{DMGT_2021_41_1_a19,
     author = {Plachta, Leonid},
     title = {Coverings of {Cubic} {Graphs} and {3-Edge} {Colorability}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {311--334},
     publisher = {mathdoc},
     volume = {41},
     number = {1},
     year = {2021},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2021_41_1_a19/}
}
TY  - JOUR
AU  - Plachta, Leonid
TI  - Coverings of Cubic Graphs and 3-Edge Colorability
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2021
SP  - 311
EP  - 334
VL  - 41
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2021_41_1_a19/
LA  - en
ID  - DMGT_2021_41_1_a19
ER  - 
%0 Journal Article
%A Plachta, Leonid
%T Coverings of Cubic Graphs and 3-Edge Colorability
%J Discussiones Mathematicae. Graph Theory
%D 2021
%P 311-334
%V 41
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2021_41_1_a19/
%G en
%F DMGT_2021_41_1_a19
Plachta, Leonid. Coverings of Cubic Graphs and 3-Edge Colorability. Discussiones Mathematicae. Graph Theory, Tome 41 (2021) no. 1, pp. 311-334. http://geodesic.mathdoc.fr/item/DMGT_2021_41_1_a19/

[1] R. Diestel, Graph Theory (Springer, Berlin, Heidelberg, 2010). doi: 10.1007/978-3-642-14279-6

[2] M.A. Fiol, G. Mazzuoccolo and E. Steffen, On measures of edge-uncolorability of cubic graphs: A brief survey and some new results, 23 Feb 2017. arXiv:1702.07156v1[math.CO]

[3] M. Ghebleh, The circular chromatic index of Goldberg snarks, Discrete Math. 307 (2007) 3220–3225. doi: 10.1016/j.disc.2007.03.047

[4] J.L. Gross and T.W. Tucker, Generating all graph coverings by permutation voltage assignments, Discrete Math. 18 (1977) 273–283. doi: 10.1016/0012-365X(77)90131-5

[5] J.L. Gross and T.W. Tucker, Topological Graph Theory (Dover Publications Inc., New York, 2012).

[6] J. Hägglund, On snarks that are far from being 3-edge colorable, Electron. J. Combin. 23 (2016) #P2.6.

[7] M. Kochol, Snarks without small cycles, J. Combin. Theory Ser. B 67 (1996) 34–47. doi: 10.1006/jctb.1996.0032

[8] R. Lukoťka, E. Máčajová, J. Mazák and M. Škoviera, Small snarks with large oddness, Electron. J. Combin. 22 (2015) #P1.51.

[9] E. Máčajová and M. Škoviera, Irreducible snarks of given order and cyclic connectivity, Discrete Math. 306 (2006) 779–791. doi: 10.1016/j.disc.2006.02.003

[10] W. McCuaig, Edge reductions in cyclically k-connected cubic graphs, J. Combin. Theory Ser. B 56 (1992) 16–44. doi: 10.1016/0095-8956(92)90004-H

[11] B. Mohar, E. Steffen and A. Vodopivec, Relating embeddings and coloring properties of snarks, Ars Math. Contemp. 1 (2008) 169–184. doi: 10.26493/1855-3974.49.b88

[12] R. Nedela and M. Škoviera, Decompositions and reductions of snarks, J. Graph Theory 22 (1996) 253–279. doi: 10.1002/(SICI)1097-0118(199607)22:3(253::AID-JGT6)3.0.CO;2-L

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

[14] V.G. Vizing, Critical graphs with given chromatic class, Diskret. Analiz. 5 (1965) 9–17 (in Russian).