# Chromatic number

## Node-colouring

A **k-colouring** of a graph *G=(V,E)* is a partitioning of *V* into *k* stable sets. The **colouring number** (or chromatic number) of *G*, usually denoted by [math]\chi(G)[/math], is the smallest integer *k* for which *G* has a *k*-colouring. A colouring of *G* is **equitable** if the sizes of the colour classes differ by at most one.

Let [math]{\mathcal S}[/math] denote the family of stable sets of *G*. A **fractional colouring** of *G* is a function [math]f:{\mathcal S} \to [0;1][/math] such that [math]\sum_{S \ni v} f(S) \geq 1[/math] for every [math]v \in V[/math]. The **fractional chromatic number** is the minimum value of [math]\sum_{S \in {\mathcal S}} f(S)[/math] on fractional colourings.

A graph *G=(V,E)* is **k-list-colourable** if for arbitrary sets [math]L_v[/math] of size *k* for every [math]v \in V[/math], we can choose [math]c_v \in L_v[/math] for every [math]v \in V[/math] such that [math]c_u \neq c_v[/math] for every [math]uv \in E[/math]. A *k*-list-colouring of *G* is **equitable** if every colour appears at most [math]\lceil |V|/k\rceil[/math] times.

## Edge-colouring

A **k-edge-colouring** of a graph *G=(V,E)* is a partitioning of *E* into *k* matchings. The **edge-colouring number** (or chromatic index) of *G* is the smallest integer *k* for which *G* has a *k*-edge-colouring.

A graph *G=(V,E)* is **k-list-edge-colourable** if for arbitrary sets [math]L_e[/math] of size *k* for every [math]e \in E[/math], we can choose [math]c_e \in L_e[/math] for every [math]e \in E[/math] such that [math]c_e \neq c_f[/math] if *e* and *f* have a common end-node.

The **list-edge-colouring number** of a graph is the smallest integer *k* for which it is *k*-list-edge-colourable.