DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2018: 0.741

SCImago Journal Rank (SJR) 2018: 0.763

Rejection Rate (2018-2019): c. 84%

Discussiones Mathematicae Graph Theory

Article in press


Authors:

L. Plachta

Title:

Coverings of cubic graphs and 3-edge colorability

Source:

Discussiones Mathematicae Graph Theory

Received: 2017-10-18, Revised: 2018-09-10, Accepted: 2018-10-29, https://doi.org/10.7151/dmgt.2194

Abstract:

Let $h\colon {\tilde G}\to 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}\to G$ of uncolorable cyclically $4$-edge connected cubic graphs and an irregular $5$-fold covering $g\colon {\tilde H}\to 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

PDF
Close