= Graph coloring
{wiki}
= Graph colouring
{synonym}
A <graph coloring> assigns labels called colours to elements of a <graph>, subject to specified constraints. Here we focus on <proper vertex colouring> of a <simple graph> $G=(V,E)$: it is an <undirected graph> with a <finite set> of <vertices>, and a colouring with at most $k$ colours is a <function>
$$
c:V\to\{1,\ldots,k\},\qquad \{u,v\}\in E\Longrightarrow c(u)\ne c(v).
$$
The colour labels need not be visual colours: they can represent time slots or resources. Unused labels are allowed. Properness concerns <graph adjacency>, so moving <vertices> in a drawing does not change whether the <graph coloring> is valid.https://ocw.mit.edu/courses/6-1200j-mathematics-for-computer-science-spring-2024/mit6_1200j_s24_lec11.pdf[MIT, Graphs and Coloring, Section 2.1]{ref}
Each <colour class> $c^{-1}(i)$ is an <independent set>: no <edge> has both endpoints in it. Conversely, a <set partition> of $V$ into <independent sets> gives a proper <graph coloring> by assigning one colour to each part. Thus <graph coloring> groups mutually compatible objects, and its <chromatic number> asks for the fewest such groups.
For an illustrative scheduling model, let each <vertex> represent an activity of equal duration and each <edge> represent a pair that cannot occur in the same time slot. A proper <graph coloring> is then a schedule respecting those pairwise conflicts. If the conflicts form a <cycle graph> $C_4$ with <edges> $12,23,34,41$, activities $1,3$ can share one slot and $2,4$ another. This model assumes interchangeable slots and includes only the pairwise conflicts encoded by the <graph>.https://ocw.mit.edu/courses/6-042j-mathematics-for-computer-science-fall-2010/1ccaf180bcd244fddd32e60789fa922f_h9wxtqoa1jY.pdf[Leighton, MIT Graph Theory and Coloring, transcript pages 8–10]{ref}
The word "colouring" also occurs in <edge coloring>, which requires different colours on <edges> sharing an endpoint. The <chromatic number> discussed here always refers to <proper vertex colouring>.
Back to article page
