Proper Vertex Colorings and Color Classes

Coloring as an Assignment to Vertices

A vertex coloring assigns a color label to each vertex. The central restriction in a proper coloring is local: the endpoints of every edge must receive different labels. This way of describing a coloring makes it possible to translate between individual assignments and groups of vertices that can share a color.

Throughout, graphs are finite and simple: they have no loops or multiple edges. A set \(I\subseteq V(G)\) is independent if no two distinct vertices in \(I\) are adjacent. A partition of \(V(G)\) is a collection of pairwise disjoint, nonempty subsets whose union is \(V(G)\). For the empty vertex set, the empty collection is its partition.

The set \(C\) is the palette, or the set of available labels. A coloring can have labels in its palette that it does not use. In this tutorial, a coloring with a palette of \(k\) labels means a proper assignment into that palette; it need not use every label. When every label is used, we say explicitly that the coloring uses exactly \(k\) colors.

Color labels are names, not mathematical values that affect adjacency. For example, replacing every occurrence of red by circle and every occurrence of blue by triangle preserves whether the assignment is proper. The labels themselves may be numbers, words, symbols, or any other distinct objects.

From Color Classes to Independent Sets

Proof. First suppose \(c:V\to C\) is a proper coloring, and let \(S=c(V)\) be the set of labels it actually uses. For each \(x\in S\), the class \(c^{-1}(x)\) is nonempty by the definition of \(S\). Every vertex belongs to the class of its assigned label, so the classes have union \(V\). If a vertex belonged to both \(c^{-1}(x)\) and \(c^{-1}(y)\), then its assigned label would equal both \(x\) and \(y\), which gives \(x=y\). Thus distinct classes are disjoint. If an edge had both endpoints in \(c^{-1}(x)\), its endpoints would receive the same label \(x\), contradicting properness. Each class is therefore independent, and the nonempty classes form a partition. Their number is \(|S|\), the number of colors used.

Conversely, suppose \(\{I_1,\dots,I_r\}\) is a partition of \(V\) into independent sets, and choose distinct labels \(x_1,\dots,x_r\). Assign label \(x_i\) to every vertex in \(I_i\). Every vertex lies in exactly one part, so this defines an assignment on all of \(V\). For any edge \(uv\), its endpoints cannot lie in the same part, because each part is independent. They therefore receive different labels, so the assignment is proper. Each part is nonempty, so each of the \(r\) labels is used. If \(V=\varnothing\), the unique assignment from \(V\) has no used labels, and the corresponding partition is the empty partition; this is the \(r=0\) case. \(\square\)

This correspondence gives two equivalent ways to describe the same structure. A coloring lists the label assigned to each vertex. Its color classes group together exactly the vertices with equal labels. Conversely, a partition specifies which vertices share a label; choosing names for the parts turns it into an assignment.

Worked Examples

Labels, Classes, and the Empty Case

Proof. Let \(c:V\to C\) be an assignment, and let \(\pi\) be a one-to-one map on its used labels. Define the renamed assignment by \(c'(v)=\pi(c(v))\). For any used label \(x\), a vertex \(v\) has \(c'(v)=\pi(x)\) exactly when \(\pi(c(v))=\pi(x)\). Since \(\pi\) is one-to-one, this holds exactly when \(c(v)=x\). Therefore the class for \(\pi(x)\) under \(c'\) is the class for \(x\) under \(c\). Also, for any vertices \(u,v\), \(c(u)=c(v)\) if and only if \(\pi(c(u))=\pi(c(v))\). Thus endpoints of an edge receive different labels under \(c\) exactly when they do under \(c'\). The two assignments have the same classes and the same properness status. \(\square\)

When \(V=\varnothing\), there is exactly one function from \(V\) to any palette: the empty function. It is proper because there are no edges whose endpoint labels could violate the condition. It has no used colors and no nonempty color classes. For a nonempty graph, every assignment uses at least one color, because every vertex is assigned a label. These cases explain why the number of labels in the palette and the number of nonempty classes are different quantities.

Common Pitfall: Checking Only Some Edges

A proposed assignment is not proper merely because most edges have differently colored endpoints. For example, let \(H=(V,E)\) have \(V=\{x,y,z\}\) and \(E=\{xy,yz,zx\}\). Assign red to \(x\), red to \(y\), and blue to \(z\). A mistaken check might inspect only \(yz\) and \(zx\), observe that both edges have different endpoint labels, and call the coloring proper. But edge \(xy\) has red at both endpoints. The red class \(\{x,y\}\) is not independent, so the assignment is not proper. The correction is to check every edge, or equivalently to verify that every color class is independent.

The partition viewpoint is often convenient when the groups of vertices are already known. The assignment viewpoint is convenient when each vertex has been given a label. To move between them, take the nonempty inverse images of the labels; empty classes are discarded because partitions contain only nonempty parts. This correspondence describes proper colorings without making any claim that a coloring uses the fewest possible colors.