91Ó°ÊÓ

Show that every graph \(G\) has a vertex ordering for which the greedy algorithm uses only \(\chi(G)\) colours.

Show that the following statements are equivalent for a graph \(G\) : (i) \(\chi(G) \leqslant k\); (ii) \(G\) has an orientation without directed paths of length \(k-1\); (iii) \(G\) has an acyclic such orientation (one without directed cycles).

Prove Richardson's theorem: every directed graph without odd directed cycles has a kernel.