Math 240 Discrete Mathematics - Graph colouring

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

.. figure:: https://upload.wikimedia.org/wikipedia/commons/thumb/e/e8/Simple-bipartite-graph.svg/200px-Simple-bipartite-graph.svg.png

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 $