Chromatic number

Definition

Let $G$ be a finite graph. The chromatic number $\chi(G)$ is the smallest natural number $k$ such that $G$ is $k$ -colourable.

Remarks

For the complete graph, $\chi(K_n) = n$ . For the cycle graph $C_n$ , $\chi(C_n)$ is $2$ if $n$ is even and $3$ if $n$ is odd. A greedy colouring shows that $\chi(G) \le \Delta(G) + 1$ , where $\Delta(G)$ is the maximum degree. The chromatic number is at least the clique number.

Reading path

To understand this page from the ground up, read these 3 pages in order. The foundations come first.

Show the path as a graph

Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.

no evidence level

Graph colouring definition
K-colourable graph definition
Chromatic number definition

Where this leads

8 pages build on this one.

Tag	`0C5M7AM6FH`
URI	`m2://0C5M7AM6FH`
Kind	definition
Writing	W1 stated
MSC	05C15
Defines	Chromatic number
Uses	K-colourable graph

Chromatic number

Definition

Remarks

Reading path

Where this leads

Further reading

What this page needs for W2

What links here

Used by

Results about this