Graph Coloring & Chromatic Number Reference Cheat Sheet

Key Facts

• A proper vertex coloring assigns colors so that if $uv \in E(G)$, then $c(u) \ne c(v)$.
• The chromatic number $\chi(G)$ is the smallest integer $k$ such that $G$ has a proper $k$-coloring.
• For a complete graph $K_n$, every pair of vertices is adjacent, so $\chi(K_n) = n$.
• For a path graph $P_n$ with $n \ge 2$, the chromatic number is $\chi(P_n) = 2$.
• For a cycle graph $C_n$, $\chi(C_n) = 2$ when $n$ is even and $\chi(C_n) = 3$ when $n$ is odd.
• If $\omega(G)$ is the size of the largest clique in $G$, then $\chi(G) \ge \omega(G)$.
• For any graph $G$ with maximum degree $\Delta(G)$, the greedy coloring method gives the upper bound $\chi(G) \le \Delta(G) + 1$.
• A graph is bipartite if and only if it has no odd cycle, and every nonempty bipartite graph satisfies $\chi(G) = 2$ unless it has no edges.

Vocabulary

Graph

A graph $G = (V,E)$ is a structure made of vertices $V$ and edges $E$ connecting pairs of vertices.

Proper coloring

A proper coloring is an assignment of colors to vertices where adjacent vertices always receive different colors.

Chromatic number

The chromatic number $\chi(G)$ is the minimum number of colors needed for a proper coloring of graph $G$.

Clique

A clique is a set of vertices in which every pair of distinct vertices is connected by an edge.

Maximum degree

The maximum degree $\Delta(G)$ is the largest number of edges incident to any single vertex in $G$.

Bipartite graph

A bipartite graph is a graph whose vertices can be split into two sets so that every edge connects vertices in different sets.