Graph colouring

Definition

Let $G$ be a graph with vertex set $V$ , and let $C$ be a set, the set of colours. A colouring of $G$ with colours in $C$ is a function $c : V \to C$ such that $c(u) \neq c(v)$ for any two adjacent vertices $u$ and $v$ .

Remarks

Such a colouring is also called proper. A colouring with a set of $k$ colours is a $k$ -colouring. Each colour class $c^{-1}(x)$ is an independent set. A graph has a $2$ -colouring if and only if it is bipartite. The subject started with the colouring of maps. Francis Guthrie stated the four colour conjecture in 1852.

Where this leads

14 pages build on this one.

Tag	`0874138YP6`
URI	`m2://0874138YP6`
Kind	definition
Writing	W1 stated
MSC	05C15
Defines	Graph colouring

Graph colouring

Definition

Remarks

Where this leads

Further reading

What this page needs for W2

What links here

Used by