# Graph Colouring

Reminder from last lecture: (G=(V,E)) is (k)-colourable, if we can colour the vertices with (k) colours such that no two adjancant vertices receive the same colour. i.e. there exists a function (f:V\rightarrow{1,\dots,k}) such that for all ({u,v}) in (E), (f(u)\neq f(v))

The chromatic number (\chi(G)) is the smallest (k) such that there exists a proper (k)-colouring of (G).

## Examples

(\chi) ( 4 vertices connected in a cycle) = 2

.. image:: |filename|/math240res/images/example-4-connected.png

(\chi) ( 5 vertices connected in a cycle) = 3

.. image:: |filename|/math240res/images/example-5-connected.png

(\chi) ( 5 vertices connected in a cycle, inside there is a vertex connected to all the outer 5 vertices) = 4

.. image:: |filename|/math240res/images/example-5-1-connected.png

(\chi) (K5) = 5

.. image:: |filename|/math240res/images/example-star-pentagone.png

(\chi (K_n) = n)

(\chi (k_{n,n}) = 2)

Let (T) be a tree with (\geq 2) vertices, what is (\chi(T))?

There is a big graph T that I’m not describing… Chi(T) = 2 . The rule to colour this graph is that pick root v in V, colour w in V with 1st colour if distance from v to w is even, otherwise use 2nd colour.

## Observation: Adding edges can only increase chromatic number.

From this get if (G) contains a clique (K_k) then (\chi(G) \geq k). So (\chi(G) \geq \omega(G)) (=) size of largest clique in (G).

We say (G) is bipartite if (\chi(G) = 2), i.e. (G=(V,E)) can write (V=V_1\cup V_2) and (V_1 \cap V_2 = \emptyset), so no edge within (V_1) and no edge within (V_2).

Example of a bipartite graph

## Theorem

(G) is bipartite if and only if (G) has no cycles of odd length.

## Proof

If (G) is bipartite, then any cycle starts and ends on the “same side” of (V_1 \cup V_2) and vertices of the cycle alternate between sides. So the cycle has even length. This completes the proof.

## Next suppose (G) has no cylces of odd length.

Fix a starting vertex (V), colour (v) with colour 1. Then for each vertex (w), if (w) has even distance from (v), then give (w) colour 1, otherwise give w colour 2.

## Example

.. figure:: |filename|/math240res/images/example-graph-coloring.png

Write $D_i =$ Vertices at distance from (v). ::

D_0 D_1 D_2 …. D-i D_i+1 D_i+2

+-+ +-+ +-+ +-+ +-+ +-+ | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | +-+ +-+ +-+ +-+ +-+ +-+

## Observation

1. No edge jumps over a set (D_k). So the only way could have a “conflict” is on an edge (u,w) , where (u \in D_k), (w \in D_k). By combining the edge (u,w) with the paths from (u) to (v) and from (w) to (v), we get an odd cycle.

Fix a graph (G=(V,E)) and list its vertices as ((V_1,\dots,V_n) = L)

The greedy colouring of L colours the vertices in order, always using the smallest available integer (colour).

If a vertex has degree (k) then one of ({1,\dots,k,k+1}) is available. Thus in any case, the list never use a colour bigger than (\triangle(G) +1). This implies that (\chi(G) \leq \triangle(G) +1) for any graph.

For a planar graph (G=(V,E))

(\sum_{v\in V} d(v) = 2 |E| \leq 2 (3 |V| -6) = 6|V| -12)

So some vertex has degree 5.

Choose such a vertex and put it at the end of the list, (v_n), By induction follows that $\chi (G) \leq 6$