Authors:
L. Plachta
Title:
Coverings of cubic graphs and 3-edge colorability
Source:
Discussiones Mathematicae Graph Theory
Received 18.10.2017, Revised 10.09.2018, Accepted 29.10.2018, doi: 10.7151/dmgt.2194

Abstract:
Let h\colon {\tilde 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 {\tilde G} is 3-edge uncolorable. As particular cases, we have constructed regular and irregular 5-fold coverings f\colon {\tilde G}→ G of uncolorable cyclically 4-edge connected cubic graphs and an irregular 5-fold covering g\colon {\tilde H}→ H of uncolorable cyclically 6-edge connected cubic graphs. In \cite{S}, 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

Links:
PDF