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.