Graph Coloring and the Chromatic Number
You'll learn: How to assign colors to vertices so no two adjacent vertices share the same color, and how to find the minimum number of colors needed.
What Is Graph Coloring?
A vertex coloring of a graph assigns a color to each vertex. Think of it like coloring a map where neighboring regions must have different colors so you can distinguish them.
A proper coloring is a vertex coloring where no two adjacent vertices (vertices connected by an edge) have the same color. This is the key constraint: if vertices u and v are connected by an edge, they must receive different colors.
The Chromatic Number
The chromatic number, denoted χ(G) (Greek letter "chi"), is the smallest number of colors needed to properly color graph G.
Examples:
- A complete graph K₅ has χ(K₅) = 5, since all vertices are adjacent to each other—each needs its own color
- A bipartite graph has χ(G) = 2, since you can color one partition with one color and the other partition with a second color
- A cycle with an odd number of vertices has χ(G) = 3
- A cycle with an even number of vertices has χ(G) = 2
Why It Matters
Graph coloring solves real-world problems like:
- Scheduling: Assign time slots to exams so students taking multiple exams don't have conflicts
- Register allocation: Assign computer registers to variables in a program
- Frequency assignment: Assign radio frequencies to transmitters without interference
Finding χ(G) is computationally hard in general, but certain graph types have known chromatic numbers based on their structure.
Key Takeaway: The chromatic number χ(G) is the minimum number of colors needed for a proper vertex coloring where adjacent vertices have different colors.