Thursday, January 30, 2014

Planar graph colouring

Planar graph colouring and the art gallery theorem.

I wasn't here for this class. These notes are based on those of an unnamed but diligent student with beautiful handwriting, with some sections contributed by @xiamx.

1Colouring planar maps¶

Suppose we wish to colour the countries on a map such that no two bordering countries have the same colour.

This is equivalent to vertex-colouring a planar graph. Formally, for any $(i, j) \in E$, it must be that the colou of $i$ $\neq$ the colour of $j$.

The minimum number of colours needed to vertex-colour a graph is referred to as the chromatic number ($\chi(G)$).

1.1Four-colour theorem¶

For any planar graph $G$, $\chi(G) \leq 4$.

The only proof we have for this is a fairly inelegant one which required exhaustively checking every case using a computer. It may be possible to do this without a computer, but it hasn't been done yet.

1.2Six-colourability¶

For any planar graph $G$, $\chi(G) \leq 6$.

Proof: We can prove this by induction on $n=|V|$. One can verify the base case easily: if $n \leq 6$, obviously we can colour it with 6 or fewer colours.

Next, we assume the induction hypothesis for $n=k$. Consider $n=k+1$. By Euler's formula, we know that $m \leq 3n-6$; a corollary of this is that the minimum degree of vertices in a planar graph is strictly less than 6. Then, $G$ has a vertex, $v$, whose degree is at most 5. Let's look at $G-v$, i.e. $G$ without the vertex $v$ (with all adjacent edges removed as well). The resulting graph is clearly still planar, and what's more, by the induction hypothesis, it can be 6-coloured.

Now let's add back $v$. Well, since it has 5 or fewer neighbours, there's at least one colour (in the set of 6 colours that we can use) which hasn't yet been used by any neighbour. If we use this colour for $v$, then we have a valid 6-colouring. $\blacksquare$

1.3Five-colourability¶

For any planar graph $G$, $\chi(G) \leq 5$.

Proof: Also by induction on $n$. It's pretty long, so I'm not going to write it out in full. Has to do with alternating paths and shit.

2The art gallery theorem¶

For any museum with $n$ walls, we need at most $\displaystyle \left \lfloor \frac{n}{3} \right \rfloor$ guards.

Proof: First, we split up the floor plan into triangles, using $n-3$ non-crossing diagonals (treat diagonals as edges, wall corners as vertices). Then prove that the resulting graph is 3-colourable by induction. Put a guard at each vertices of a particular colour.