Back to Search Start Over

Subcubic edge chromatic critical graphs have many edges

Authors :
Cranston, Daniel W.
Rabern, Landon
Source :
Journal of Graph Theory. Vol. 86(1), September 2017, pp. 122-136
Publication Year :
2015

Abstract

We consider graphs $G$ with $\Delta=3$ such that $\chi'(G)=4$ and $\chi'(G-e)=3$ for every edge $e$, so-called \emph{critical} graphs. Jakobsen noted that the Petersen graph with a vertex deleted, $P^*$, is such a graph and has average degree only $\frac83$. He showed that every critical graph has average degree at least $\frac83$, and asked if $P^*$ 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^*$, then $G$ has average degree at least $\frac{46}{17}\approx2.706$. This bound is best possible, as shown by the Hajos join of two copies of $P^*$.<br />Comment: 16 pages, 10 figures; version 2 incorporates referee feedback, which led to improved exposition and a slightly stronger bound

Details

Database :
arXiv
Journal :
Journal of Graph Theory. Vol. 86(1), September 2017, pp. 122-136
Publication Type :
Report
Accession number :
edsarx.1506.04225
Document Type :
Working Paper