= Chromatic number from acyclic longest paths
{title2=$\chi(G)=\min_{D\text{ acyclic}}\lambda(D)$}
For a finite <graph>, let $\lambda(D)$ count the <vertices> on a longest <directed path> in an <acyclic orientation> $D$. Its <minimum> over those <orientation of a graph>[orientations] is the <chromatic number>. A proper $k$-colouring gives an <orientation of a graph>[orientation] from smaller to larger colours, so every <directed path> has strictly increasing colours and at most $k$ <vertices>. Conversely, assign to each <vertex> the number of <vertices> in a longest <directed path> ending there. Along an <edge> $u\to v$ this number increases: an ending <graph path>[path] at $u$ cannot contain $v$ without forming a <directed cycle>, so it can be extended. The resulting labels give a proper <colouring> using at most $\lambda(D)$ colours. These two constructions prove equality. <Counting> <edges> instead of <vertices> in <graph path>[path] length subtracts one from the displayed <minimum>.
Back to article page
