Departure question
Read the world behind shapePort 12 of 13Begin with lengths and angles, then move toward less visible properties of space: connection, holes, and dimension.
This voyage is an editorial path for understanding, not a claim of direct historical influence or sole invention.
"How few colors do you need so adjacent regions never share a color?" A student's 1852 question led, 124 years later, to the Four Color Theorem — one of the first major theorems whose proof depended on computer checking. School timetabling, radio-frequency allocation, and compiler register allocation can all be modeled as graph coloring.
Graph type | χ(G) | Real-world application |
|---|---|---|
Planar map (Four Color Theorem) | ≤ 4 | Political maps, GIS |
Bipartite graph (no odd cycle) | 2 | Student-course matching |
n-clique (Kₙ) | n | Complete graph |
Odd cycle | 3 | Timetable conflicts |
Petersen graph | 3 | A standard textbook example |
Tree | 2 | Hierarchical structures |
χ(G) is the chromatic number of G: the minimum number of colors needed so adjacent vertices differ. Computing it in general is NP-complete.
Coloring nodes so neighbors differ — from maps to compilers to scheduling.
Ports in time
Follow the scenes to see problems, notation, standards of proof, and applications changing across different times and places.
Francis Guthrie conjectured that four colors would suffice for every planar map after coloring a map of English counties.
No reliable place is given, so time continues without an invented pin
Continue through the world of this yearKenneth Appel and Wolfgang Haken completed the first famous computer-assisted proof of a major theorem.
No reliable place is given, so time continues without an invented pin
Continue through the world of this yearComplexity theory established that deciding whether a graph can be colored with three colors is NP-complete, exposing the difficulty of graph coloring in general.
No reliable place is given, so time continues without an invented pin
Continue through the world of this yearCompiler register allocation, timetable scheduling, frequency assignment, GIS maps, and collision avoidance in graphics workloads.
Curated sources and problems. Bring one discovery back from OEIS, Project Euler, MathOverflow, or arXiv.
No concept belongs to one person
These are not inventor credits. They are different ports: opening a problem, sharpening a language, or carrying it into another world.
Number lenses
These numbers are editorial lenses for the voyage, not required prerequisites.
Begin with lengths and angles, then move toward less visible properties of space: connection, holes, and dimension.
Open the number voyage
Begin with lengths and angles, then move toward less visible properties of space: connection, holes, and dimension.
Open the number voyage
Begin with lengths and angles, then move toward less visible properties of space: connection, holes, and dimension.
Open the number voyage
Concept genealogy
Concepts arriving from before
Current port
Graph Coloring
Concepts opened from here
Only direct editorial links are shown; this is not a complete learning order or historical influence line.
