An improved bound on the minimal number of edges in color-critical graphs

Abstract

A graph $G$ is $k$-color-critical (or simply $k$-critical) if $\chi(G)=k$ but $\chi(G') < k$ for every proper subgraph $G'$ of $G$, where $\chi(G)$ denotes the chromatic number of $G$. Consider the following problem: given $k$ and $n$, what is the minimal number of edges in a $k$-critical graph on $n$ vertices? It is easy to see that every vertex of a $k$-critical graph $G$ has degree at least $k-1$, implying $|E(G)|\geq {{k-1}\over {2}}|V(G)|$. Gallai improved this trivial bound to $|E(G)|\geq {{k-1}\over {2}}+{{k-3}\over {2(k^2-3)}}|V(G)|$ for every $k$-critical graph $G$ (where $k\geq 4$), which is not a clique $K_k$ on $k$ vertices. In this note we strengthen Gallai's result by showing

Theorem Suppose $k\geq 4$, and let $G=(V,E)$ be a $k$-critical graph on more than $k$ vertices. Then $ |E(G)|\geq ({{k-1}\over {2}}+{{k-3}\over {2(k^2-2k-1)}})|V(G)| $