Subcubic edge chromatic critical graphs have many edges

Abstract

We consider graphs $G$ with $\Delta =3$ such that ${\chi }^{\prime }(G)=4$ and ${\chi }^{\prime }(G-e)=3$ for every edge $e$, so-called \emph{critical} graphs. Jakobsen noted that the Petersen graph with a vertex deleted, $P^{\ast }$, is such a graph and has average degree only $\frac{8}{3}$. He showed that every critical graph has average degree at least $\frac{8}{3}$, and asked if $P^{\ast }$ is the only graph where equality holds. A result of Cariolaro and Cariolaro shows that this is true. We strengthen this average degree bound further. Our main result is that if $G$ is a subcubic critical graph other than $P^{\ast }$, then $G$ has average degree at least $\frac{46}{17}\approx 2.706$. This bound is best possible, as shown by the Hajos join of two copies of $P^{\ast }$.

16 pages, 10 figures; version 2 incorporates referee feedback, which led to improved exposition and a slightly stronger bound