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 |
|
|