Skip to main content

Section 14.3 Vertex colouring

Suppose you have been given the task of assigning broadcast frequencies to transmission towers. You have been given a list of frequencies that you are permitted to assign. There is a constraint: towers that are too close together cannot be assigned the same frequency, since they would interfere with each other.

One way to approach this problem is to model it as a graph. The vertices of the graph will represent the towers, and the edges will represent towers that can interfere with each other. Your job is to assign a frequency to each of the vertices. Instead of writing a frequency on each vertex, we will choose a colour to represent that frequency, and use that colour to colour the vertices to which you assign that frequency.

Here is an example of this.

This graph represents the towers and their interference patterns.

This represents a possible assignment of 4 colours to the vertices. The colour of each vertex (red, green, blue, or yellow) is indicated by writing the first letter of the colour's name on the vertex).

Notice that this colouring obeys the constraint that interfering towers are not assigned the same frequencies.

Definition 14.3.2.

A proper \(k\)-vertex-colouring (or just \(k\)-colouring) of a graph \(G\) is a function that assigns to each vertex of \(G\) one of \(k\) colours, such that adjacent vertices must be assigned different colours.

As with edge-colouring, the constraint that adjacent vertices receive different colours turns out to be a useful constraint that arises in many contexts. We often represent the \(k\) colours by the numbers \(1, \ldots, k\text{,}\) and label the vertices with the appropriate numbers rather than colouring them.

Definition 14.3.3.

A graph \(G\) is \(k\)-colourable if it admits a proper \(k\)-(vertex-)colouring. The smallest integer \(k\) for which \(G\) is \(k\)-colourable is called the chromatic number of \(G\text{.}\)

Notation 14.3.4.

The chromatic number of \(G\) is denoted by \(\chi(G)\), or simply by \(\chi\) if the context is unambiguous.

We leave the proof of the following as an exercise (see Exercise 14.3.14.2).

Prove that for a graph \(G\text{,}\) \(\chi(G)=2\) if and only if \(G\) is a bipartite graph that has at least one edge.

Proof

\(\boldsymbol{(\Rightarrow)}\) Suppose that \(\chi(G)=2\text{.}\) Take a proper \(2\)-colouring of \(G\) with colours \(1\) and \(2\text{.}\) Let \(V_1\) denote the set of vertices of colour \(1\text{,}\) and let \(V_2\) denote the set of vertices of colour \(2\text{.}\) Since the colouring is proper, there are no edges both of whose endvertices are in \(V_1\) (as these would be adjacent vertices both coloured with colour \(1\)). Similarly, there are no edges both of whose endvertices are in \(V_2\text{.}\) Thus, the sets \(V_1\) and \(V_2\) form a bipartition of \(G\text{,}\) so \(G\) is bipartite. Since \(2\) colours were required to properly colour \(G\text{,}\) \(G\) must have at least one edge.

\(\boldsymbol{(\Leftarrow)}\) Suppose that \(G\) is bipartite, and that \(V_1\) and \(V_2\) form a bipartition of \(G\text{.}\) Colour the vertices in \(V_1\) with colour \(1\text{,}\) and colour the vertices of \(V_2\) with colour \(2\text{.}\) By the definition of a bipartition, no pair of adjacent vertices can have been assigned the same colour. Thus, this is a proper \(2\)-colouring of \(G\text{,}\) so \(\chi(G)\le 2\text{.}\) Since \(G\) has at least one edge, the endpoints of that edge must be assigned different colours, so \(\chi(G)\ge 2\text{.}\) Thus \(\chi(G)=2\text{.}\)

Show that for any \(n\ge 1\text{,}\) \(\chi(C_{2n+1})=3\text{.}\)

Solution

Since this graph has an edge whose endvertices must be assigned different colours, we see that \(\chi(C_{2n+1})\ge 2\text{.}\) Since a cycle of odd length is not bipartite (see Theorem 14.1.13), Example 14.3.6 shows that \(\chi(C_{2n+1}) \neq 2\text{,}\) so \(\chi(C_{2n+1})\ge 3\text{.}\) Let the cycle be \((u_1, u_2, \ldots, u_{2n+1},u_1)\text{.}\) Since the only edges in the graph are between consecutive vertices in this list, if we assign colour \(1\) to \(u_1\text{,}\) colour \(2\) to \(u_{2i}\) for \(1 \le i \le n\text{,}\) and colour \(3\) to \(u_{2i+1}\) for \(1 \le i \le n\text{,}\) this will be a proper \(3\)-colouring. Thus, \(\chi(C_{2n+1})=3\text{.}\)

Definition 14.3.8.

A graph \(G\) is \(k\)-critical if \(\chi(G)=k\text{,}\) but for every proper subgraph \(H\) of \(G\text{,}\) \(\chi(H)\lt \chi(G)\text{.}\)

Towards a contradiction, suppose that \(G\) is a disconnected \(k\)-critical graph, and let \(G_1\) and \(G_2\) be (nonempty) subgraphs of \(G\) such that every vertex of \(G\) is in either \(G_1\) or \(G_2\text{,}\) and there is no edge from any vertex in \(G_1\) to any vertex in \(G_2\text{.}\) By the definition of \(k\)-critical, \(\chi(G_1)\lt \chi(G)\) and \(\chi(G_2)\lt \chi(G)\text{.}\) But if we colour \(G_1\) with \(\chi(G_1)\) colours and \(G_2\) with \(\chi(G_2)\) colours, since there is no edge from any vertex of \(G_1\) to any vertex of \(G_2\text{,}\) this produces a proper colouring of \(G\) with

\begin{equation*} \max(\chi(G_1),\chi(G_2))\lt \chi(G) \end{equation*}

colours. This contradiction serves to prove that every \(k\)-critical graph is connected.

⬛

Towards a contradiction, suppose that \(G\) is \(k\)-critical and has a vertex \(v\) of valency at most \(k-2\text{.}\) By the definition of \(k\)-critical, \(G\setminus\{v\}\) must be \((k-1)\)-colourable. Now, since \(v\) has no more than \(k-2\) neighbours, its neighbours can be assigned at most \(k-2\) distinct colours in this colouring. Therefore, amongst the colours used in the \((k-1)\)-colouring of \(G\setminus\{v\}\text{,}\) there must be a colour that is not assigned to any of the neighbours of \(v\text{.}\) If we assign this colour to \(v\text{,}\) the result is a proper \((k-1)\)-colouring of \(G\text{,}\) contradicting \(\chi(G)=k\text{.}\) This contradiction serves to prove that every \(k\)-critical graph has minimum valency at least \(k-1\text{.}\)

⬛

Let \(G\) be an arbitrary graph. By deleting as many edges and vertices as it is possible to delete without reducing the chromatic number (we can never increase the chromatic number by deleting vertices or edges, see Exercise 14.3.14.1), we see that \(G\) must have a subgraph \(H\) that is \(\chi(G)\)-critical. By Theorem 14.3.10, we see that

\begin{equation*} \delta(H) \ge \chi(G)-1\text{.} \end{equation*}

Thus, every vertex of \(H\) has valency at least \(\chi(G)-1\text{,}\) so in \(G\text{,}\) these same vertices still have valency at least \(\chi(G)-1\text{.}\) For any such vertex \(v\text{,}\) we have

\begin{equation*} \Delta(G)\ge d(v)\ge\chi(G)-1\text{,} \end{equation*}

so \(\chi(G)\le \Delta(G)+1\text{.}\)

⬛

We have already seen two families of graphs for which this bound is attained: for complete graphs, we have

\begin{equation*} \Delta(K_n)+1=(n-1)+1=n=\chi(K_n) \end{equation*}

(see Proposition 14.3.5); and for cycles of odd length, we have

\begin{equation*} \Delta(C_{2n+1})+1=2+1=3=\chi(C_{2n+1}) \end{equation*}

(see Example 14.3.7). In fact, Rowland Leonard Brooks (1916—1993) proved in \(1941\) that these are the only connected graphs for which this bound is obtained.

We will not include the proof of this result in this course. This theorem does allow us to determine the chromatic number of some graphs with very little work.

The following very famous graph is called the Petersen graph, named for Peter Christian Julius Petersen (1839—1910). It is an exceptional graph in many ways, so when mathematicians are trying to come up with a proof or a counterexample in graph theory, it is often one of the first examples they will check. Find its chromatic number.

Solution

We have \(\Delta=3\text{,}\) and since this graph is neither a complete graph nor a cycle of odd length, by Brooks' Theorem this shows that \(\chi \le 3\text{.}\) We can find a cycle of length 5 around the outer edge of the graph, so this graph is not bipartite but has an edge. Therefore (by Example 14.3.6), \(\chi >2\text{.}\) Hence \(\chi=3\text{.}\)

  1. Prove that if \(H\) is a subgraph of \(G\) then \(\chi(G) \ge \chi(H)\text{.}\)

  2. Prove Proposition 14.3.5 by induction.

  3. Prove Corollary 14.3.11 by induction for every graph on at least one vertex.

  4. For each \(i,j \in \{4,5,6\}\text{,}\) suppose you are given a graph \(G\) that contains a subgraph isomorphic to \(K_i\) and no vertex has more than \(j\) neighbours. What (if anything) can you say about \(\chi(G)\text{?}\) Can you say more if you know that \(G\) is connected and is neither a complete graph nor a cycle of odd length?

For each of the following graphs, determine its chromatic number by using theoretical arguments to provide a lower bound, and then producing a colouring that meets the bound. Do the same for the edge-chromatic number.

We have seen that the largest complete subgraph of a graph provides a lower bound on the chromatic number of the graph. In general, this isn't a very good lower bound, and we've certainly seen examples where it is not achieved.

Definition 14.3.16.

A graph \(G\) is a perfect graph if for every induced subgraph \(H\) of \(G\text{,}\) the chromatic number \(\chi(H)\) is equal to the number of vertices in the largest complete subgraph of \(H\text{.}\)

A characterisation of perfect graphs had long been conjectured, but was finally proved in \(2006\text{.}\) Although Maria Chudnovsky (1977—), George Neil Robertson (1938—), Paul Seymour (1950—), and Robin Thomas (1962—2020) were involved in this proof and are credited with the theorem, it is the main result in the Ph.D. thesis of Chudnovsky.

Note that any cycle of odd length has chromatic number \(3\text{,}\) but its largest complete subgraph is \(K_2\text{,}\) so such a graph can certainly not be perfect, and therefore by definition any graph having such an induced subgraph cannot be perfect. This is less obvious in the case of the complement of an odd cycle. We will not try to prove in general that the complement of an odd cycle is not perfect, but we provide an illustrative example.

The following graph is the complement of a cycle of length \(7\text{.}\) Its largest complete subgraph is a \(K_3\text{.}\) However, if we colour any of its triangles with three colours and determining all of the colours that would be forced by that beginning in a proper \(3\)-colouring, it is not hard to see that \(4\) colours are required in a proper colouring.

We also provide an example of a perfect graph.

This graph is perfect.

Its largest complete subgraph has three vertices (any column of vertices). It can be properly coloured with \(3\) colours.