Chromatic number from acyclic longest paths

ID: chromatic-number-from-acyclic-longest-paths

For a finite graph, let count the vertices on a longest directed path in an acyclic orientation . Its minimum over those orientations is the chromatic number. A proper -colouring gives an orientation from smaller to larger colours, so every directed path has strictly increasing colours and at most vertices. Conversely, assign to each vertex the number of vertices in a longest directed path ending there. Along an edge this number increases: an ending path at cannot contain without forming a directed cycle, so it can be extended. The resulting labels give a proper colouring using at most colours. These two constructions prove equality. Counting edges instead of vertices in path length subtracts one from the displayed minimum.

New to topics? Read the docs here!