The Coloring Problem

Graph Theory · Axiom Academy

Can you color a graph so no two neighbors share the same color? Step 1: The Triangle Challenge Here's your first puzzle: Three friends all know each other. Can you assign each person a color so that no two friends have the same color ? Step 2: The Two-Color Challenge Now try something different. This graph has 4 vertices. Can you color it using only 2 colors ? Here's a more complex graph. What's the minimum number of colors you need? Try starting with 2 colors, then add more if you get stuck! Graph coloring is the problem of assigning colors to vertices so that no two adjacent vertices (connected by an edge) share the same color. The goal is often to find the minimum number of colors needed. The chromatic number χ(G) of a graph G is the smallest number of colors needed to properly color the graph. For example: a triangle has χ = 3, while a simple path or cycle of even length has χ = 2. Scheduling: Assign time slots to exams so no student has conflicts. Map coloring: Color countries so neighbors have different colors. Register allocation: Assign computer registers to variables in compilers.

This is the written version of the interactive lesson above. See the full Graph Theory course.