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\longrightarrow k$

such that $c(u)\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}\,\}.$

This minimum exists. Since $V$ is finite, there is a bijection $b:V\to |V|$ (The cardinality $\lvert A\rvert$ of a finite set), and $b$ is a proper $|V|$-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=\varnothing$. Its unique empty function $\varnothing\to0$ is a proper $0$-colouring, so $\chi(G)=0$. Conversely, a nonnull graph has no function from its nonempty vertex set to $0=\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)\leq\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 $\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\{\,|S|:S\subseteq V\text{ is independent}\,\},\qquad \omega(G):=\max\{\,|K|:K\subseteq V\text{ is a clique}\,\}.$

These maxima are well-defined. Every subset of the finite set $V$ is finite and has cardinality at most $|V|$ (A subset of a finite set is finite, with $\lvert B\rvert \le \lvert A\rvert$, and equality holds if and only if $B = A$). Thus the sizes occurring in either display form a subset of $\{0,\ldots,|V|\}$ that contains $0$, since the empty subset is both independent and a clique. A short induction on $|V|$ 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)\leq\chi(G),\qquad |V|\leq\chi(G)\alpha(G).$

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