Coverings of Cubic Graphs and 3-Edge Colorability

Abstract

Let h:G˜→Gh:\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 G˜\tilde G is 3-edge uncolorable. As particular cases, we have constructed regular and irregular 5-fold coverings f:G˜→Gf:\tilde G \to G of uncolorable cyclically 4-edge connected cubic graphs and an irregular 5-fold covering g:H˜→Hg:\tilde H \to H of uncolorable cyclically 6-edge connected cubic graphs.

Keywords

• uncolorable cubic graph
• covering of graphs
• voltage permutation graph
• resistance
• nowhere-zero 4-flow
• 05c15
• 05c10