Chromatic number, the four color theorem, and applications
Color the vertices so that no two neighbors match, using as few colors as you can. The same puzzle schedules exams and colors every map.
Pick a color from the palette and click vertices to paint them. Try each preset graph with as few colors as possible.
Click a vertex to color it with the selected color
Graph coloring assigns labels (called "colors") to vertices so that no two adjacent vertices share the same color. The minimum number of colors needed for a proper coloring is called the chromatic number of the graph.
Finding the chromatic number is NP-hard in general, but greedy algorithms provide fast approximations. The celebrated Four Color Theorem guarantees that every planar graph can be properly colored with at most four colors. Graph coloring also models practical problems such as exam scheduling and register allocation.
Complete graphs Kn require exactly n colors, bipartite graphs need only 2, and odd cycles need 3. The chromatic number captures the essential "conflict density" of a graph.
Press Run Greedy, then Shuffle Order and run it again. Notice that the number of colors used changes with the order.
The greedy algorithm processes vertices in a fixed order, assigning each the smallest color not used by its already-colored neighbors. Greedy coloring runs in O(V + E) time but does not always achieve the optimal chromatic number. The result depends entirely on the vertex ordering, and some orderings may use far more colors than necessary.
Pick a color and click regions to paint the map with at most four colors. Hover over a region to highlight its neighbors.
Click a region to color it. Hover to see adjacent regions highlighted.
The Four Color Theorem states that any map can be colored with at most four colors so that no two adjacent regions share a color. First conjectured in 1852, the Four Color Theorem was proven in 1976 by Appel and Haken using computer-assisted proof -- the first major theorem to require computational verification.
Click an exam, then choose a time slot, or press Auto Schedule. Exams joined by an edge share students, so they need different slots.
Click an exam to select it, then choose a time slot below
Graph coloring models real scheduling problems. Here, exams are vertices and edges connect exams with shared students. Colors represent time slots. Graph coloring appears in register allocation (variables that overlap in lifetime cannot share a register), frequency assignment (adjacent transmitters need different frequencies), and even Sudoku puzzles.
Spot a mistake or have an idea?