# Graph Colouring

• We have seen several problems where it doesn't seem like graph theory should be useful.
• … 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.
• When drawing a map, we want to be able to distinguish different regions.
• 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.
• e.g. I coloured the provinces of Canada with three colours:
• But it took four colours for China:
• 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?
• Again, we can reresent this problem as a graph to get the useful information, while throwing away details we don't care about.
• 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).
• For example…
• We reduce it to this graph:
• Now the question becomes: how many colours do we need to colour this (or any other) graph so that no two adjacent vertices have the same colour?
• 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.

• In general, the chromatic number could be large.
• For example, a $$K_n$$ requires $$n$$ colours since every vertex is adjacent to every other.
• But, if we get our graph from a map, it will be planar.
• 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?
• Easy bound: it's at least four.
• The graph $$K_4$$ is planar and definitely requires four colours.
• It's easy to show that the chromatic number of a planar graph is no more than six.
• 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.
• Getting $$\le 5$$ isn't much harder.
• 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.
• That leaves us with a question: are there planar graphs that require five colours?
• 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.

• So, it turns out we can colour any (planar) map with four colours.
• 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.
• But remember:
• 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 Applications

• Actually colouring maps is a good motivation for the chromatic number problem, but maybe not all that practical.
• 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.
• There are other places where a colouring of a graph tells us something interesting.
• These are really just examples of where the problem comes up in an unexpected place.
• Scheduling exams
• 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.
• Register allocation
• 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.
• Sudoku
• 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.
• If we might actually want to find colourings to solve real problems, how quickly can we find them?
• 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.