Chromatic number

The chromatic number $\chi (G)$ is the least number of colours in a proper vertex colouring of $G$.

A vertex $v$ is colour-critical if deleting it lowers the chromatic number by one. If $\chi (F)=r+1$ and $\chi (F-v)=r$, an embedding of $F-v$ into a complete $r$-partite graph inside one neighbourhood extends to an embedding of $F$. This supplies maximum-degree obstructions in extremal graph theory.

The Mycielski construction replaces a graph $G$ with a graph $\mu (G)$ having one shadow vertex for each original vertex and one further vertex adjacent to every shadow. It satisfiesand preserves triangle-freeness. Iterating it from the five-cycle gives triangle-free graphs of arbitrarily large chromatic number.

For every $g,k\ge 3$, there is a finite graph with no cycle of length at most $g$ and with chromatic number at least $k$. A probabilistic proof samples a sparse binomial random graph, observes that it has few short cycles and no large independent set, and deletes one vertex from every short cycle.

A connected graph of maximum degree $\Delta$ has chromatic number at most $\Delta$ unless it is a complete graph or an odd cycle.