Double-critical graph conjecture for claw-free graphs

Martin Rolek, Zi-Xia Song

Published 2016-10-03Version 1

A connected graph $G$ with chromatic number $t$ is \dfn{double-critical} if $G - x - y$ is $(t-2)$-colorable for each edge $xy\in E(G)$. The complete graphs are the only known examples of double-critical graphs. A long-standing conjecture of Erd\H os and Lov\'asz from 1966, which is referred to as the \dfn{Double-critical Graph Conjecture}, states that there are no other double-critical graphs, i.e., if a graph $G$ with chromatic number $t$ is double-critical, then $G=K_t$. This has been verified for $t \le 5$, but remains open for $t \ge 6$. In this paper, we first prove that if $G$ is a non-complete double-critical graph with chromatic number $t \ge 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 \le 8$ if $G$ is claw-free.