• … but graphs are often very good at capturing the important stuff about a problem, so we can see it clearly.
• This is going to be another one of those.

• One of the ways that's done is by drawing them in different colours.
• …with the rule that regions that touch each other must be different colours: otherwise we couldn't see the border.

• But it took four colours for China:

  
  Derived from Wikipedia Map_of_PRC.svg

• Could I have coloured China with three colours?
• Are there countries that take five colours? Six?
• Could there be such countries if they had weird-enough borders?

• Each region will be a vertex.
• Connect verticies with edges if they share a border (that's larger than a point: they can touch at a corner and we don't care).

• We start with this map with six regions:

• We reduce it to this graph:

• A solution (coloured graph) is called a colouring.
• The minimum number of colours needed for a colouring of a graph is its chromatic number.

Theorem: Every bipartite graph has chromatic number two.

Proof: By definition, bipartite graphs can have their vertices partitioned into two sets with no edges within the sets. Colour the vertices from each partition the same colour, and we have a colouring.∎

• For example, a \(K_n\) requires \(n\) colours since every vertex is adjacent to every other.

• As long as we don't allow enclaves and exclaves, and we won't.
• So the question becomes: what is the maximum chromatic number for a planar graph?

• The graph \(K_4\) is planar and definitely requires four colours.

• We know there is a vertex of degree five or less from an earlier theorem.
• Remove that vertex, and by induction, the rest of the graph can be coloured.
• Colour it a different colour than the adjacent five.

• There's a little trick to show that the five adjacent vertices didn't have to be different colours.
• … but don't worry about the details.

• It turns out: no.

Theorem: [The Four-Colour Theorem] The chromatic number of a planar graph is at most four.

Proof: It took more than 100 years between conjecture and proof for this theorem. The proof involved reducing the planar graphs to about 2000 examples where if the theorem was false, it was shown one of these would be a counter-example. These each had 4-colourings found by computer.

Obviously, we won't go into the details.

• The four-colour theorem is one that seems true: a little experimenting would convince most people that the chromatic number can be at most four.
• But the proof turned out to be very difficult.

• The chromatic number of non-planar graphs can be more than four: for example \(n\) for \(K_n\).
• The chromatic number of non-planar graphs can also be small: 2 for \(K_{10000,100000}\).

• Colouring the maps we actually have on the planet doesn't need a big theorem.
• It's hard to see why we would care about non-planar graphs.

• These are really just examples of where the problem comes up in an unexpected place.

• Let the vertices of the graph be the courses, and connect vertices with an edge if there are any students in both courses.
• We'll end up with a graph like this (but bigger):

• If we can colour this with \(n\) colours, then we need \(n\) exam slots.
• … and courses in each colour can be scheduled at the same time.

• Registers are pieces of memory in a processor that are much faster than standard RAM.
• When your code is compiled by an optimizing compiler, it will attempt to use the registers when appropriate to speed up your code.
• e.g. the index on a for loop is probably used a lot: maybe use a register for it?
• But there is a limited number registers.
• Create a graph: vertices are variables in the code; edges join them if the variables are used in the same segment of code.
• If we can colour the graph with \(n\) colours, then we can use \(n\) registers for all of the variables.
• Variables with the same colour can share a register, swapping them out when necessary.

• Create one vertex for each of the 81 squares.
• Join vertices if they cannot have the same value assigned: if they are in the same row/column/square.
• Create some extra edges to enforce the pre-filled values.
• Find a nine-colouring.

• Again, we don't know of any fast algorithm.
• Apparently, we can find a colouring of \(n\) vertices in \(O(2.445^n)\) or \(O(2^n n)\).
• There are some reasonably-fast approximation algorithms: we can colour a graph quickly if we are willing to accept a few more colours than necessary.