Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
5776917 | Discrete Mathematics | 2017 | 6 Pages |
Abstract
A connected graph G with chromatic number t is double-critical if Gâ{x,y} is (tâ2)-colorable for each edge xyâE(G). The complete graphs are the only known examples of double-critical graphs. A long-standing conjecture of ErdÅs and Lovász from 1966, which is referred to as the Double-Critical Graph Conjecture, states that there are no other double-critical graphs. That is, if a graph G with chromatic number t is double-critical, then G is the complete graph on t vertices. This has been verified for tâ¤5, but remains open for tâ¥6. In this paper, we first prove that if G is a non-complete, double-critical graph with chromatic number tâ¥6, then no vertex of degree t+1 is adjacent to a vertex of degree t+1, t+2, or t+3 in G. We then use this result to show that the Double-Critical Graph Conjecture is true for double-critical graphs G with chromatic number tâ¤8 if G is claw-free.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Martin Rolek, Zi-Xia Song,