k-Coloring — Definition, Formula & Examples

A k-coloring of a graph is an assignment of at most

k

distinct colors to the graph's vertices such that no two vertices connected by an edge receive the same color. If a valid k-coloring exists, the graph is called k-colorable.

Given a graph $G = (V, E)$ and a positive integer $k$ , a proper $k$ -coloring is a function $c: V \to \{1, 2, \ldots, k\}$ such that $c(u) \neq c(v)$ for every edge $\{u, v\} \in E$ . The chromatic number $\chi(G)$ is the smallest $k$ for which a proper $k$ -coloring of $G$ exists.

How It Works

To find a k-coloring, you try to label each vertex with one of

k

colors while ensuring every pair of adjacent vertices gets different colors. Start by picking any vertex and assigning it color 1. Move to an adjacent vertex and assign the lowest-numbered color that does not conflict with its already-colored neighbors. Repeat until all vertices are colored or you discover that

k

colors are insufficient. If you succeed, the graph is

k

-colorable; if not, you need more colors. The minimum

k

that works is the chromatic number

\chi(G)

Worked Example

Problem: Determine whether the cycle graph

C_4

(a square with vertices

v_1, v_2, v_3, v_4

and edges forming a cycle) is 2-colorable.

Step 1: Assign color 1 to

v_1

. Its neighbor

v_2

must differ, so assign color 2 to

v_2

c(v_1) = 1,\quad c(v_2) = 2

Step 2:

v_3

is adjacent to

v_2

(color 2), so assign color 1 to

v_3

. Then

v_4

is adjacent to both

v_3

(color 1) and

v_1

(color 1), so assign color 2 to

v_4

c(v_3) = 1,\quad c(v_4) = 2

Step 3: Check all edges:

(v_1,v_2)

1 \neq 2

(v_2,v_3)

2 \neq 1

(v_3,v_4)

1 \neq 2

(v_4,v_1)

2 \neq 1

. Every edge has differently colored endpoints.

Answer: Yes,

C_4

is 2-colorable. Its chromatic number is

\chi(C_4) = 2

Why It Matters

Graph coloring appears directly in scheduling problems (assigning time slots so conflicting events don't overlap), register allocation in compilers, and map coloring. The Four Color Theorem — every planar graph is 4-colorable — is one of the most famous results in mathematics, and understanding k-colorings is the foundation for studying it.

Common Mistakes

Mistake: Confusing k-colorable with requiring exactly k colors.

Correction: A k-coloring uses at most k colors. A graph that is 3-colorable is automatically 4-colorable, 5-colorable, and so on. The chromatic number

\chi(G)

is the minimum k needed.