Graph Colouring: short notes (Engineering Mathematics)

Introduction

Colouring a graph means giving each vertex a colour so that adjacent vertices get different colours. Colours stand for resources and edges for conflicts: exam slots for courses that share students, frequencies for nearby transmitters, machine registers for variables that are live at the same time (register allocation in a compiler, see Liveness Analysis). The minimum number of colours needed is the chromatic number. Computing it is NP-hard in general, so the development concentrates on exact values for structured graphs, on bounds, and on counting colourings.

Prerequisites

Graph Theory Fundamentals: special graphs, bipartite graphs, planar graphs, degrees. Graphs are simple and undirected; a graph with a loop cannot be properly coloured.

Core concepts

Proper colouring and chromatic number

A proper $k$ -colouring of $G$ is a function $c : V \to \{1, \ldots, k\}$ with $c(u) \ne c(v)$ for every edge $\{u, v\}$ . $G$ is $k$ -colourable if one exists. The chromatic number $\chi(G)$ is the least such $k$ .

Each colour class is an independent set, so a $k$ -colouring partitions $V$ into at most $k$ independent sets, one for each colour actually used.

Chromatic numbers of standard graphs

Graph	$\chi$
Graph with no edges ( $n \ge 1$ )	1
Any bipartite graph with at least one edge (trees, even cycles, $K_{r,s}$ , $Q_k$ )	2
Cycle $C_n$	2 if $n$ even, 3 if $n$ odd
Complete graph $K_n$	$n$
Wheel $W_n$ (hub + $C_n$ )	3 if $n$ even, 4 if $n$ odd
Petersen graph	3
Any planar graph	at most 4

Characterisation of $\chi \le 2$ : $\chi(G) \le 2$ if and only if $G$ is bipartite, if and only if $G$ has no odd cycle. There is no comparable simple test for $\chi \le 3$ ; deciding 3-colourability is NP-complete.

Colourings of cycles, wheels, bipartite and planar graphs — Figure 1. Optimal colourings of $C_6$ (2 colours), $C_5$ (3), $W_5$ (4), $K_{3,3}$ (2) and a planar graph needing 4 colours ( $K_4$ ), with colours written as numbers on the vertices.

Bounds

Let $\omega(G)$ be the size of a largest clique (complete subgraph), $\alpha(G)$ the size of a largest independent set and $\Delta(G)$ the maximum degree.

\max\!\left(\omega(G),\ \left\lceil \frac{n}{\alpha(G)} \right\rceil\right) \;\le\; \chi(G) \;\le\; \Delta(G) + 1 .

Lower bounds. A clique of size $\omega$ needs $\omega$ colours. Each colour class has at most $\alpha$ vertices, so $\chi \cdot \alpha \ge n$ .
Upper bound by greedy colouring. Colour vertices in any order, giving each the smallest colour not used by its already-coloured neighbours. A vertex has at most $\Delta$ neighbours, so at most $\Delta + 1$ colours are used.
Brooks' theorem. If $G$ is connected and is neither a complete graph nor an odd cycle, then $\chi(G) \le \Delta(G)$ . The two exceptions are exactly where $\Delta + 1$ is needed.
$\chi$ can be much larger than $\omega$ : there are triangle-free graphs ( $\omega = 2$ ) with arbitrarily large chromatic number (Mycielski's construction; the Grotzsch graph has $\omega = 2$ , $\chi = 4$ ).
Greedy depends on the order. On a bipartite graph a bad order can force many colours. For the "crown" graph ( $K_{k,k}$ minus a perfect matching, $k\ge2$ ) with vertices taken in the order $a_1, b_1, a_2, b_2, \ldots$ , greedy uses $k$ colours although $\chi = 2$ .

Planar graphs

Four colour theorem (Appel and Haken, 1976): every planar graph satisfies $\chi \le 4$ . The proof is computer-assisted.
The five colour theorem has a short proof using the fact that a planar graph has a vertex of degree at most 5.
The bound 4 is tight ( $K_4$ is planar). Colouring the regions of a map so that neighbouring regions differ is the same as colouring the vertices of its dual graph, which is planar.

The chromatic polynomial

$P(G, k)$ is the number of proper colourings of $G$ using colours from a set of $k$ colours (colourings that differ only by which colour goes where count as different). Then $\chi(G)$ is the least positive integer $k$ with $P(G, k) > 0$ .

Graph	$P(G, k)$
$n$ isolated vertices	$k^n$
$K_n$	$k(k-1)(k-2)\cdots(k-n+1)$
Any tree on $n$ vertices	$k(k-1)^{n-1}$
Cycle $C_n$	$(k-1)^n + (-1)^n (k-1)$
Disjoint union $G_1 \cup G_2$	$P(G_1, k)\, P(G_2, k)$

Deletion-contraction: for any edge $e$ ,

P(G, k) = P(G - e, k) - P(G / e, k),

where $G - e$ deletes $e$ and $G / e$ merges its endpoints (removing duplicate edges). The colourings of $G - e$ split into those that give the ends of $e$ different colours (the colourings of $G$ ) and those that give them the same colour (the colourings of $G / e$ ).

Properties: $P(G, k)$ is a polynomial in $k$ of degree $n$ , with leading coefficient 1; the coefficient of $k^{n-1}$ is $-m$ ; the constant term is 0.

Edge colouring

A proper edge colouring gives adjacent edges (sharing an endpoint) different colours; each colour class is a matching. The chromatic index $\chi'(G)$ is the least number of colours.

$\chi'(G) \ge \Delta(G)$ always.
Vizing's theorem: $\chi'(G) = \Delta$ or $\Delta + 1$ for every simple graph.
Konig's edge-colouring theorem: for bipartite graphs, $\chi'(G) = \Delta(G)$ .
$\chi'(K_1)=0$ ; for $n\ge2$ , $\chi'(K_n) = n - 1$ if $n$ is even and $n$ if $n$ is odd. (Round-robin tournaments: with $n$ even, $n - 1$ rounds suffice.)
$\chi'(C_n) = 2$ for even $n$ and 3 for odd $n$ . The Petersen graph has $\chi' = 4$ although $\Delta = 3$ .

See Matching in Graphs for matchings.

Worked examples

Example 1: chromatic number by bounds

$G$ = $C_5$ with one chord added (vertices 1 to 5 in a cycle, chord $\{1, 3\}$ ). It contains the triangle 1, 2, 3, so $\chi \ge 3$ . A 3-colouring: $c(1) = 1, c(2) = 2, c(3) = 3, c(4) = 1, c(5) = 2$ . Hence $\chi = 3$ .

Example 2: chromatic polynomials

$P(K_3, k) = k(k-1)(k-2)$ . With 3 colours: $3 \cdot 2 \cdot 1 = 6$ colourings.
$P(C_4, k) = (k-1)^4 + (k-1)$ . With 3 colours: $16 + 2 = 18$ . With 2 colours: $1 + 1 = 2$ .
A path on 4 vertices (a tree): $P = k(k-1)^3$ . With 3 colours: $3 \cdot 8 = 24$ .
$C_5$ with 3 colours: $2^5 - 2 = 30$ ; with 2 colours: $1 - 1 = 0$ , confirming $\chi(C_5) = 3$ .

Example 3: deletion-contraction on $C_4$

Delete an edge of $C_4$ : a path $P_4$ with $k(k-1)^3$ colourings. Contract it: $K_3$ (the triangle $C_3$ ), with $k(k-1)(k-2)$ . So

P(C_4, k) = k(k-1)^3 - k(k-1)(k-2) = k(k-1)(k^2 - 3k + 3),

which equals $(k-1)^4 + (k-1)$ on expanding.

Example 4: exam scheduling

Five courses; pairs sharing a student: AB, AC, BC, CD, DE, EA. The conflict graph contains the triangle A, B, C, so at least 3 slots. Slots: A = 1, B = 2, C = 3, D = 1, E = 2. Check: CD (3, 1), DE (1, 2), EA (2, 1) are all different. Minimum: 3 slots.

Important properties and observations

$\chi(G) \le 1 +$ the length of a longest path (a greedy argument along a DFS tree).
$\chi(G) + \chi(\overline{G}) \le n + 1$ .
Removing a vertex lowers $\chi$ by at most 1. Adding an edge raises it by at most 1.
A graph with $m$ edges has $\chi(\chi - 1)/2 \le m$ (every two colour classes must be joined by an edge in an optimal colouring).
Counting colourings with "exactly $k$ colours used" is different from $P(G, k)$ , which counts colourings from $k$ available colours.

GATE examination perspective

Chromatic number of a given graph. Find a clique for the lower bound, then exhibit a colouring that matches it. Check odd cycles for $\chi \ge 3$ .
Special families. $C_n$ , $W_n$ , $K_n$ , $K_{r,s}$ , trees, planar graphs. Watch which wheel convention is used (hub + $C_n$ here).
Chromatic polynomial evaluation. Trees, cycles and complete graphs by formula; others by deletion-contraction.
Bounds statements. $\omega \le \chi \le \Delta + 1$ ; Brooks; $\chi \alpha \ge n$ .
Trap: $\chi = \omega$ is not true in general ( $C_5$ : $\omega = 2$ , $\chi = 3$ ).
Trap: the four colour theorem is about planar graphs only; $K_5$ needs 5 colours.

Summary

$\chi(G)$ : fewest colours with adjacent vertices different; colour classes are independent sets.
$\chi \le 2$ if and only if bipartite; $\chi(C_n) = 2$ or 3; $\chi(K_n) = n$ ; $\chi(W_n) = 3$ or 4; planar $\le 4$ .
$\omega\le\chi\le\Delta+1$ . For connected $G$ , Brooks gives $\chi\le\Delta$ unless $G$ is complete or an odd cycle. Also $\chi\ge n/\alpha$ .
$P(K_n, k) = k(k-1)\cdots(k-n+1)$ ; tree $k(k-1)^{n-1}$ ; $C_n$ : $(k-1)^n + (-1)^n(k-1)$ ; $P(G) = P(G - e) - P(G/e)$ .
Edge colouring: $\Delta \le \chi' \le \Delta + 1$ ; bipartite $\chi' = \Delta$ ; $\chi'(K_1)=0$ ; for $n\ge2$ , $\chi'(K_n) = n - 1$ for even $n$ , $n$ for odd $n$ .
$\chi = \omega$ fails in general: $C_5$ has $\omega = 2$ , $\chi = 3$ ; $K_5$ needs 5 colours and is not planar.

Graph Theory Fundamentals: prerequisite. Bipartite and planar graphs.
Matching in Graphs: related. Edge colour classes are matchings; independent sets and vertex covers.
Liveness Analysis: dependent. Register allocation colours the interference graph.

Graph Colouring

Introduction

Prerequisites

Core concepts

Proper colouring and chromatic number

Chromatic numbers of standard graphs

Bounds

Planar graphs

The chromatic polynomial

Edge colouring

Worked examples

Example 1: chromatic number by bounds

Example 2: chromatic polynomials

Example 3: deletion-contraction on $C_4$

Example 4: exam scheduling

Important properties and observations

GATE examination perspective

Summary

Sources

Next steps

Introduction

Prerequisites

Core concepts

Proper colouring and chromatic number

Chromatic numbers of standard graphs

Bounds

Planar graphs

The chromatic polynomial

Edge colouring

Worked examples

Example 1: chromatic number by bounds

Example 2: chromatic polynomials

Example 3: deletion-contraction on C4C_4C4​

Example 4: exam scheduling

Important properties and observations

GATE examination perspective

Summary

Related topics

Sources

Next steps

Example 3: deletion-contraction on $C_4$