Vertex Coloring and Chromatic Number

Graph coloring assigns labels to vertices so that adjacent vertices receive different labels. The minimum number of colors needed -- the chromatic number -- is a fundamental and computationally hard graph invariant.

Basic Definitions

Definition5.1Proper Coloring and Chromatic Number

A proper $k$ -coloring of a graph $G$ is a function $c: V(G) \to \{1, \ldots, k\}$ such that $c(u) \neq c(v)$ whenever $uv \in E(G)$ . The chromatic number $\chi(G)$ is the minimum $k$ for which a proper $k$ -coloring exists. A graph is $k$ -colorable if $\chi(G) \leq k$ , and $k$ -chromatic if $\chi(G) = k$ . Determining $\chi(G)$ is NP-hard in general, even deciding if $\chi(G) \leq 3$ .

Definition5.2Greedy Coloring and Degeneracy

The greedy algorithm processes vertices in some order $v_1, \ldots, v_n$ and assigns each $v_i$ the smallest color not used by its already-colored neighbors. This gives $\chi(G) \leq \Delta(G) + 1$ where $\Delta$ is the maximum degree. The degeneracy $d(G)$ is the minimum $k$ such that every subgraph has a vertex of degree $\leq k$ . Ordering vertices by repeatedly removing minimum-degree vertices gives $\chi(G) \leq d(G) + 1$ . The degeneracy ordering is computable in $O(n + m)$ time.

Bounds on Chromatic Number

ExampleClique Number vs. Chromatic Number

The clique number $\omega(G) \leq \chi(G)$ (a clique of size $k$ needs $k$ colors). Equality need not hold: the Mycielski construction builds triangle-free ( $\omega = 2$ ) graphs with arbitrarily large $\chi$ . The Kneser graph $K(n,k)$ (vertices = $k$ -subsets of $[n]$ , edges = disjoint pairs) has $\chi(K(n,k)) = n - 2k + 2$ (Lovász, 1978, using topological methods) while $\omega(K(n,k)) = \lfloor n/k \rfloor$ .

RemarkBrooks' Theorem

Brooks' theorem: If $G$ is connected and not a complete graph or odd cycle, then $\chi(G) \leq \Delta(G)$ . The proof constructs a specific vertex ordering for greedy coloring: root a spanning tree, use BFS/DFS ordering, and ensure each vertex (except possibly the root) has a neighbor colored later, allowing the greedy algorithm to use at most $\Delta$ colors. The exceptions $K_n$ and $C_{2k+1}$ genuinely need $\Delta + 1$ colors.