91Ó°ÊÓ

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

For every \(n>1\), find a bipartite graph on \(2 n\) vertices, ordered in such a way that the greedy algorithm uses \(n\) rather than 2 colours.

A \(k\)-chromatic graph is called critically \(k\)-chromatic, or just critical, if \(\chi(G-v)

Show that every critical \(k\)-chromatic graph is \((k-1)\)-edge-connected.

Show that, in order to prove Brooks's theorem for a graph \(G=(V, E)\), we may assume that \(\kappa(G) \geqslant 2\) and \(\Delta(G) \geqslant 3\). Prove the theorem under these assumptions, showing first the following two lemmas. (i) Let \(v_{1}, \ldots, v_{n}\) be an enumeration of \(V\). If every \(v_{i}(ii\), and if \(v_{1} v_{n}, v_{2} v_{n} \in E\) but \(v_{1} v_{2} \notin E\), then the greedy algorithm uses at most \(\Delta(G)\) colours. (ii) If \(G\) is not complete and \(v_{n}\) has maximum degree in \(G\), then \(v_{n}\) has neighbours \(v_{1}, v_{2}\) as in (i).

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).

Given a graph \(G\) and \(k \in \mathbb{N}\), let \(P_{G}(k)\) denote the number of vertex colourings \(V(G) \rightarrow\\{1, \ldots, k\\} .\) Show that \(P_{G}\) is a polynomial in \(k\) of degree \(n:=|G|\), in which the coefficient of \(k^{n}\) is 1 and the coefficient of \(k^{n-1}\) is \(-\|G\| .\) ( \(P_{G}\) is called the chromatic polynomial of \(G .\) ) (Hint. Apply induction on \(\|G\| .\) )

An \(n \times n\) - matrix with entries from \(\\{1, \ldots, n\\}\) is called a Latin square if every element of \(\\{1, \ldots, n\\}\) appears exactly once in each column and exactly once in each row. Recast the problem of constructing Latin squares as a colouring problem.

Without using Theorem 5.4.2, show that every plane graph is 6-listcolourable.

Does every oriented graph have a kernel? If not, does every graph admit an orientation in which every induced subgraph has a kernel? If not, does every graph admit an orientation that has a kernel?