Graph Coloring & Cliques

Coloring asks how few colors you can get away with; cliques explain why some graphs refuse to cooperate.

The idea

A proper vertex coloring of a graph $G$ assigns a color to every vertex so that no edge has both endpoints the same color, and the chromatic number $\chi(G)$ is the smallest number of colors for which a proper coloring of $G$ exists. The colors are labels for an assignment: to schedule exams so that no student sits two at once, make the exams vertices, join two exams whenever some student takes both, and properly color the graph — the colors are the time slots, and $\chi(G)$ is the fewest slots that suffice.

A clique in $G$ is a set of vertices every two of which are joined by an edge, and the clique number $\omega(G)$ is the number of vertices in the largest clique of $G$. The complete graph $K_{n}$ has $n$ vertices with every pair joined, so it is a clique on $n$ vertices.

The two numbers are related: the vertices of a clique are pairwise adjacent, so a proper coloring must give a clique of size $r$ exactly $r$ different colors, and therefore $\omega(G) \le \chi(G)$ for every graph $G$.

Ways to work on it

• Walkthrough. Meet chromatic number, clique number, and their basic relationship.
• Practice. Compute the chromatic number or clique number of standard small graphs.
• Hardest. Use clique bounds and bipartite structure to reason about coloring.

Not sure where to start? Take the ten-question placement test.