Graph Colouring

Let $G=(V,E)$ be a finite simple graph (A finite simple graph is a finite vertex set together with a set of two-element vertex subsets) and let $k\in \mathbb{N}$. A proper $k$-vertex-colouring is a function

$c:V⟶k$

such that $c(u)\mathrm{\ne }c(v)$ whenever $\{u,v\}\in E$. Its fibres are the colour classes. The graph is $k$-colourable when such a function exists.

The chromatic number of $G$ is

$\chi (G):=\min \{k\in \mathbb{N}:G\text{ is }k\text{-colourable}\}\mathrm{.}$

This minimum exists. Since $V$ is finite, there is a bijection $b:V\to \mathrm{\mid }V\mathrm{\mid }$ (The cardinality $\mid A\mid$ of a finite set), and $b$ is a proper $\mathrm{\mid }V\mathrm{\mid }$-colouring because adjacent vertices are distinct. The displayed set of admissible natural numbers is therefore nonempty, so it has a least element by The well-ordering principle.

The null graph has $V=\mathrm{\varnothing }$. Its unique empty function $\mathrm{\varnothing }\to 0$ is a proper $0$-colouring, so $\chi (G)=0$. Conversely, a nonnull graph has no function from its nonempty vertex set to $0=\mathrm{\varnothing }$, and hence has positive chromatic number. Colours are labels only: composing a proper colouring with a bijection of its colour set changes no adjacency condition.

Let $G=(V,E)$ be a nonnull finite simple graph. Then

$\chi (G)\le \mathrm{\Delta }(G)+1.$

More precisely, after the vertices are put in any finite order, assigning to each vertex the least colour not already used by an earlier neighbour produces a proper colouring with colours in $\mathrm{\Delta }(G)+1$.

Let $G=(V,E)$ be a finite simple graph. A subset $S\subseteq V$ is independent, or stable, when no two distinct elements of $S$ are adjacent. A subset $K\subseteq V$ is a clique when every two distinct elements of $K$ are adjacent.

The independence number and clique number are

$\alpha (G):=\max \{\mathrm{\mid }S\mathrm{\mid }:S\subseteq V\text{ is independent}\},\omega (G):=\max \{\mathrm{\mid }K\mathrm{\mid }:K\subseteq V\text{ is a clique}\}\mathrm{.}$

These maxima are well-defined. Every subset of the finite set $V$ is finite and has cardinality at most $\mathrm{\mid }V\mathrm{\mid }$ (A subset of a finite set is finite, with $\mid B\mid \le \mid A\mid$, and equality holds if and only if $B=A$). Thus the sizes occurring in either display form a subset of $\{0,\dots ,\mathrm{\mid }V\mathrm{\mid }\}$ that contains $0$, since the empty subset is both independent and a clique. A short induction on $\mathrm{\mid }V\mathrm{\mid }$ shows that every such subset has a largest element: either its top element occurs, or it is a subset of the preceding finite ordinal and the induction hypothesis applies (The principle of mathematical induction). In particular, for the null graph one has $\alpha (G)=\omega (G)=0$; for every nonnull graph both values are at least $1$.

For every finite simple graph $G=(V,E)$,

$\omega (G)\le \chi (G),\mathrm{\mid }V\mathrm{\mid }\le \chi (G)\alpha (G)\mathrm{.}$

Both inequalities include the null graph, where all displayed quantities are $0$.

Let $c$ be a proper vertex colouring of a graph $G$ (Proper vertex colourings and chromatic number) and let $a\mathrm{\ne }b$ be colours. The $a$-$b$ Kempe subgraph is the subgraph induced by the vertices whose colours lie in $\{a,b\}$ (Subgraphs, induced subgraphs and spanning subgraphs). An $a$-$b$ Kempe chain is a connected component of this induced subgraph (Connected graphs and connected components defined by the existence of vertex paths).

The word chain denotes a connected component, not necessarily a graph-theoretic path. A path inside a Kempe chain alternates colours because the ambient colouring is proper.

Let $c$ be a proper colouring, let $a\mathrm{\ne }b$, and let $K$ be one $a$-$b$ Kempe component (Kempe chains as connected components induced by two colour classes, Connected graphs and connected components defined by the existence of vertex paths). Interchanging $a$ and $b$ on $K$ and leaving all other colours fixed gives another proper colouring.