Subcubic Edge‐Chromatic Critical Graphs Have Many Edges |
| |
| Authors: | Daniel W Cranston Landon Rabern |
| |
| Institution: | 1. DEPARTMENT OF MATHEMATICS AND APPLIED MATHEMATICS, VIRIGINIA COMMONWEALTH UNIVERSITY, RICHMOND, VAContract grant sponsor: National Security Agency;2. contract grant number: H98230‐15‐1‐0013 (to D.W.C.).;3. LBD DATA SOLUTIONS, LANCASTER, PA |
| |
| Abstract: | We consider graphs G with  such that  and  for every edge e, so‐called critical graphs. Jakobsen noted that the Petersen graph with a vertex deleted,  , is such a graph and has average degree only  . He showed that every critical graph has average degree at least  , and asked if  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  , then G has average degree at least  . This bound is best possible, as shown by the Hajós join of two copies of  . |
| |
| Keywords: | chromatic index critical edge‐coloring |
|
|
such that 
and 
for every edge e, so‐called critical graphs. Jakobsen noted that the Petersen graph with a vertex deleted, 
, is such a graph and has average degree only 
. He showed that every critical graph has average degree at least 
, and asked if 
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 
, then G has average degree at least 
. This bound is best possible, as shown by the Hajós join of two copies of 
.