Past exam of the graph theory course of the University of Oxford / 2011 / 2 / b / iii / Solution

Part (ii) shows that $\chi (G)\le \lambda (D)$ for every acyclic orientation $D$, so $\chi (G)$ is at most their minimum. Part (i), applied to an optimal colouring, supplies an acyclic orientation with $\lambda (D)\le \chi (G)$. Combining the inequalities givesThe parameter counts vertices on a graph path; if graph path length were instead counted in edges, the corresponding minimum would be $\chi (G)-1$.

These constructions prove chromatic number from acyclic longest paths.