---
tag: 0874138YP6
kind: definition
name: Graph colouring
msc: [05C15]
defines: 0NCPXH194Y
sources:
  - url: https://en.wikipedia.org/wiki/Graph_coloring
    locator: Definition and terminology
---

## Definition

Let $G$ be a [[graph|0JD5C82QMB]] 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|0KZJ82WEPP]].
A graph has a $2$-colouring if and only if it is [[bipartite|07DVHJ8N0A]].
The subject started with the colouring of maps. Francis Guthrie stated the four colour conjecture in 1852.

## Explanations

### L1 human

Colour the vertices of a graph so that the two ends of each edge have different colours.
For example, a timetable gives each exam a time slot, so that exams with a common student are at different times.