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: |