# 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 $\chi(G)$, 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 ${\mathcal S}$ denote the family of stable sets of G. A fractional colouring of G is a function $f:{\mathcal S} \to [0;1]$ such that $\sum_{S \ni v} f(S) \geq 1$ for every $v \in V$. The fractional chromatic number is the minimum value of $\sum_{S \in {\mathcal S}} f(S)$ on fractional colourings.

A graph G=(V,E) is k-list-colourable if for arbitrary sets $L_v$ of size k for every $v \in V$, we can choose $c_v \in L_v$ for every $v \in V$ such that $c_u \neq c_v$ for every $uv \in E$. A k-list-colouring of G is equitable if every colour appears at most $\lceil |V|/k\rceil$ 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 $L_e$ of size k for every $e \in E$, we can choose $c_e \in L_e$ for every $e \in E$ such that $c_e \neq c_f$ 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.