Skip to main content

Section 14.3 Colouring vertices

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

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{.}\)

The proof is by induction on the number of vertices.

Base case: \(n=1\text{.}\) The only graph on one vertex is \(K_1\text{,}\) so \(G \cong K_1\text{.}\) This can be properly coloured with \(1\) colour (and requires one colour), so \(\chi(G)=1\text{.}\) Also \(\Delta(G)=0\text{,}\) so

\begin{equation*} \chi(G)=1 \le 0+1=\Delta(G)+1, \end{equation*}

as claimed.

Induction step: Let \(k \ge 1\) be arbitrary, and assume that for every graph \(H\) on \(k\) vertices, we have \(\chi(H) \le \Delta(H)+1\text{.}\) Now let \(G\) be an arbitrary graph on \(k+1\) vertices. Let \(v\) be an arbitrary vertex of \(G\text{,}\) and let \(G'\) be the graph obtained by deleting \(v\text{.}\) We may vertex-colour \(G'\) with \(\chi(G')\) colours. Clearly, \(G'\) has \(k\) vertices, so by our induction hypothesis, we have

\begin{equation*} \chi(G') \le \Delta(G')+1 \le \Delta(G) + 1 . \end{equation*}

Therefore, we have coloured the vertices in \(V(G')\) with at most \(\Delta(G)+1\) colours. The only remaining vertex that needs to be coloured is \(v\text{.}\) Since the valency of \(v\) is at most \(\Delta(G)\text{,}\) its neighbours use at most \(\Delta(G)\) of these colours, so there is at least one colour that has not been used to colour any neighbour of \(v\text{.}\) We may use this remaining colour on \(v\text{,}\) in order to produce a proper colouring of \(G\) with at most \(\Delta(G)+1\) colours.

We have shown that every graph on \(1\) vertex has \(\chi \le \Delta+1\text{,}\) and that if every graph on \(k\) vertices has \(\chi \le \Delta+1\) then so does every graph on \(k+1\) vertices, where \(k \ge 1\text{.}\) Hence by the Principle of Mathematical Induction, every graph on at least one vertex has \(\chi \le \Delta +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. Assume \(G\) is a graph, and \(G'\) is the graph obtained by deleting a vertex \(v\text{.}\)

    1. Show that \(\chi(G) \le \chi(G') + 1\text{.}\)

    2. Show that if \(d_G(v) < \chi(G')\text{,}\) then \(\chi(G) = \chi(G')\text{.}\)

  3. Prove Proposition 14.3.5 by induction.

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

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.