Back to Search
Start Over
Subcubic edge chromatic critical graphs have many edges
- 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
- Subjects :
- Mathematics - Combinatorics
05C15, 05C35
Subjects
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