c-Critical graphs with maximum degree three

Abstract

Let $G$ be a (simple) gtoph with maximum degree three and chromatic index four. A 3-edge-coloring of G is a coloring of its edges in which only three colors are used. Then a vertex is conflicting when some edges incident to it have the same color. The minimum possible number of conflicting vertices that a 3- edge-coloring of G can have is called the edge-coloring degree, $d(G)$, of $G$. Here we are mainly interested in the structure of a graph $G$ with given edge-coloring degree and, in particula.r, when G is c-critical, that is $d(G) = c \ge 1$ and $d(G - e) < c$ for any edge $e$ of $G$.

Peer Reviewed

Postprint (author’s final draft)