Discrete Math · Undergraduate
Graph Coloring and the Chromatic Number
Quick answer
A coloring of a graph gives each vertex a color so that the two ends of every edge get different colors. The chromatic number χ(G) is the fewest colors that work. A complete graph Kₙ needs n colors, an even cycle needs 2 and an odd cycle needs 3. A graph can be colored with 2 colors exactly when it has no odd cycle. Coloring solves scheduling problems: vertices are events, edges are conflicts, and colors are time slots.
What you'll learn
- Color a graph and find its chromatic number
- Prove lower bounds with triangles, odd cycles and complete subgraphs
- Decide whether a graph is two-colorable
- Model a scheduling problem as a coloring problem
Neighbors get different colors
A coloring of a graph assigns each vertex a color so that the two ends of every edge have different colors. The chromatic number is the fewest colors that work.
Coloring models conflicts. Suppose five exams, Math, Physics, Chemistry, Biology and English, must be scheduled, and an edge joins two exams that share a student. Exams of the same color can run at the same time, so is the fewest time slots.
Why an odd cycle needs three colors
Walk around a cycle with only two colors available. Each step crosses an edge, so the color must switch: the vertices alternate red, blue, red, blue. After an odd number of steps the walk returns to its start on the opposite color from the one it began with, which is a contradiction. An odd cycle cannot be two-colored, so any graph that contains one needs at least three colors.
The converse also holds. If a connected graph has no odd cycle, color each vertex by whether its distance from a fixed vertex is even or odd; this always works. Graphs with are called bipartite.
Bounds on χ
- A complete subgraph inside forces , since its vertices are all neighbors.
- Greedy coloring gives each vertex in turn the first color its colored neighbors are not using. With largest degree , at most colors are blocked, so .
- Every planar graph has : the four color theorem.
Worked examples
Common mistakes
Practice problems
-
Find .
Answer
Full solution
All six vertices are neighbors, so all six colors must differ.
-
Find and .
Answer
and
Full solution
Even cycles alternate two colors; odd cycles need a third.
-
What is the chromatic number of a tree with vertices?
Answer
Full solution
A tree has no cycles at all, so no odd cycles, and it has at least one edge.
-
Find for a wheel with a -vertex rim.
Answer
Full solution
The even rim takes colors and the hub a third. A hub and two neighboring rim vertices form a triangle, so is not enough.
-
Every vertex of a graph has degree at most . What does greedy coloring guarantee?
Answer
At most colors
Full solution
.
-
Is a -cycle bipartite?
Answer
No
Full solution
It is an odd cycle, so it needs colors.
-
Committees A, B, C and D meet weekly. A and B share a member, as do B and C, C and D, and D and A. What is the fewest number of meeting times?
Answer
Full solution
The conflict graph is the -cycle A–B–C–D–A, so A and C meet at one time and B and D at another.
-
A student colors a graph greedily, uses colors, and concludes . What is wrong?
Answer
Greedy coloring gives only an upper bound; may be smaller.
Full solution
A different order may use fewer colors. To prove , the student needs a reason colors fail, such as a or a wheel with an odd rim.
Frequently asked questions
What is the chromatic number of a graph?
The smallest number of colors needed to color the vertices so that every edge joins two different colors. It is written χ(G).
When can a graph be colored with two colors?
Exactly when it has no cycle of odd length. Such graphs are called bipartite.
What is the chromatic number of a cycle?
2 if the cycle has an even number of vertices, 3 if it has an odd number.
How many colors does greedy coloring use?
At most Δ + 1, where Δ is the largest degree, since each vertex has at most Δ neighbors already colored. The order of the vertices affects how many it uses.
What is the four color theorem?
Every planar graph can be colored with at most 4 colors. So any map can be colored with 4 colors so that bordering regions differ.