Graph Coloring: Chromatic Numbers & Four Color Theorem
Explore graph theory concepts including chromatic numbers, the Four Color Theorem, and real-world applications in scheduling and networks.
Graph Coloring
Chromatic Numbers, The Four Color Theorem & Real-World Applications
Mathematics | Graph Theory
Examples of Chromatic Numbers
Path Graph
Vertices connected in a straight line • Alternate two colors
→ χ(G) = 2
Even Cycle
Colors alternate perfectly • Example: Square graph
→ χ(G) = 2
Odd Cycle
Alternating pattern breaks at last vertex • A third color is needed
→ χ(G) = 3
Complete Graph K₄
Every vertex connects to every other • No color can be reused
→ χ(G) = 4
In a complete graph with n vertices, the chromatic number is n.
Applications of Graph Coloring
Real-world conflict problems solved through coloring.
Exam Scheduling
Subjects = vertices. Edge = shared students. Same-color subjects scheduled together.
Compiler Design
Variables sharing CPU registers are colored differently to avoid conflicts.
Mobile Networks
Nearby towers use different frequencies — each frequency acts as a color.
Sudoku
Numbers behave like colors. Constraints mirror graph coloring rules.
Graph coloring converts conflict problems into coloring problems.
Introduction to the Four Color Problem
"Can any map always be colored using only four colors?"
Neighboring countries cannot share the same color.
This became one of the most famous problems in graph theory.
→ Each region = vertex. Shared border = edge.
Example: A 4-colored map
Four Color Theorem
Every planar graph can be colored using at most four colors such that adjacent regions do not share the same color.
What is Planar?
A graph that can be drawn on a plane without any edges crossing.
Key Insight
Even the most complex maps require only 4 colors. No map has ever required 5 colors.
No map has EVER required 5 colors.
History of the Four Color Problem
1852
Francis Guthrie
First proposed the four color conjecture while coloring a map of England.
1852–1976
Many Failed Proofs
For over 100 years, mathematicians attempted to prove it — all failed.
1976
Kenneth Appel & Wolfgang Haken
Finally proved it using a computer — one of the first major theorems solved with computer assistance.
First major mathematical theorem proved with the help of a computer.
Why Was It Difficult?
Infinite possible maps
— no finite set of cases to check
Complex region arrangements
— unpredictable configurations
Enormous number of cases
— too many for any human to verify
Traditional Proofs
Humans could not manually verify all possibilities
Computer-Assisted
Checked thousands of configurations automatically
Graph Coloring Algorithms
Greedy Coloring Algorithm
Pick a vertex
Assign the smallest available color
Continue sequentially through all vertices
✓ Simple & fast
⚠ May not give minimum colors
Welsh-Powell Algorithm
Sort vertices by degree (highest first)
Color vertices with highest degree first
Usually gives better results than greedy
Scheduling
Optimization
Network Allocation
Greedy = Fast. Welsh-Powell = Smarter order.
Complexity & Challenges
Graph coloring is NP-hard.
As graphs grow larger, finding the exact minimum number of colors becomes exponentially more difficult.
Easy: small graphs
Impossible: large graphs
The Problem
No fast universal algorithm exists for all graphs.
The Solutions
Approximation algorithms & Heuristics used in real systems.
Modern Applications
AI & Machine Learning
Used in constraint solving, optimization, and resource allocation problems.
Wireless Communication
Prevents signal interference by assigning different frequencies to nearby towers.
Operating Systems
Efficient register and resource allocation for processes running simultaneously.
Transportation
Train scheduling and traffic signal management to avoid conflicts.
Summary
Graph coloring prevents conflicts between connected elements.
The chromatic number gives the minimum colors required.
Planar maps require at most four colors — the Four Color Theorem.
Applications exist across scheduling, networks, AI, and beyond.
Graph Coloring — Key Takeaways
Quiz Time! 🎯
Let's test what we've learned.
Can a triangle graph be colored using only 2 colors?
Yes ✓
No ✗
Answer: No!
A triangle is an odd cycle (3 vertices all connected). The last vertex always conflicts — you need 3 colors. χ(G) = 3
Think before you answer!
Thank You
Any questions?
Graph Coloring — Mathematics & Graph Theory
- graph-theory
- mathematics
- discrete-math
- algorithms
- computer-science
- four-color-theorem
- education