Subcubic edge chromatic critical graphs have many edges
Daniel W. Cranston, Landon Rabern · 2015
We consider graphs G with ∆ = 3 such that χ′(G) = 4 and χ′(G − e) = 3 for every edge e, so-called critical graphs. Jakobsen noted that the Petersen graph with a vertex deleted, P ∗, is such a graph and has average degree only 2 + 23. He showed that every critical graph has average degree at least 2+ 23, and asked if P ∗ is the only graph where equality holds. We answer his question affirmatively. Our main result is that every subcubic critical graph, other than P ∗, has average degree at least 2 + 2637 = 2.702. 1