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.