Equality cases for a bound on the chromatic number

Abstract

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 equality holds whenever the graph consists of a complete graph or an odd cycle, together with finitely many trees attached to its vertices.

5 pages