Equality cases for a bound on the chromatic number

Boon Suan Ho, Joel Junyao Tan, Xiaorui Zhang

It is known that the inequality $$\frac{\chi (G)(\chi (G)-1)}{2}+|V|-\chi (G)\le |E|$$ holds for all connected graphs, where $\chi (G)$ denotes the chromatic number of $G$. We prove that eq…