On the density of critical graphs with no large cliques

Abstract

A graph $G$ is \textit{$k$-critical} if $\chi (G)=k$ and every proper subgraph of $G$ is $(k-1)$-colorable, and if $L$ is a list-assignment for $G$, then $G$ is \textit{$L$-critical} if $G$ is not $L$-colorable but every proper induced subgraph of $G$ is. In 2014, Kostochka and Yancey proved a lower bound on the average degree of an $n$-vertex $k$-critical graph tending to $k-\frac{2}{k-1}$ for large $n$ that is tight for infinitely many values of $n$, and they asked how their bound may be improved for graphs not containing a large clique. Answering this question, we prove that for $\epsilon \le 2.6\cdot 10^{-10}$, if $k$ is sufficiently large and $G$ is a $K_{\omega +1}$-free $L$-critical graph where $\omega \le k-{\log }^{10}k$ and $L$ is a list-assignment for $G$ such that $|L(v)|=k-1$ for all $v\in V(G)$, then the average degree of $G$ is at least $(1+\epsilon )(k-1)-\epsilon \omega -1$. This result implies that for some $\epsilon >0$, for every graph $G$ satisfying $\omega (G)\le \mathrm{mad}(G)-{\log }^{10}\mathrm{mad}(G)$ where $\omega (G)$ is the size of the largest clique in $G$ and $\mathrm{mad}(G)$ is the maximum average degree of $G$, the list-chromatic number of $G$ is at most $\lceil (1-\epsilon )(\mathrm{mad}(G)+1)+\epsilon \omega (G)\rceil$.

27 pages; to appear in Combinatorica

References in corpus (2)

• An improved procedure for colouring graphs of bounded local density
• A local epsilon version of Reed's Conjecture

Cited by in corpus (1)

• Sparse $4$-critical graphs have low circular chromatic number