Course contentsShow
← Mathematics
Lesson 2696 of 3,12153. Graph TheoryFree lesson

Coloring Special Graphs

Determine chromatic numbers for bipartite graphs, complete graphs, cycles, and trees.

Coloring Special Graphs

You'll learn how to determine the chromatic number for common families of graphs with predictable structures.

In the previous lesson, you learned that the chromatic number χ(G) is the minimum number of colors needed to color a graph's vertices so no adjacent vertices share a color. For many special graph families, we can determine χ(G) exactly using their structural properties.

Bipartite Graphs

A bipartite graph has vertices split into two independent sets with edges only between sets, never within. Since no two vertices in the same set are adjacent, we can color one set with color 1 and the other with color 2. Therefore, χ(G) = 2 for any connected bipartite graph (or 1 if it's just isolated vertices).

Complete Graphs

In a complete graph Kₙ, every vertex connects to every other vertex. Each vertex must have a unique color since it's adjacent to all others. Thus, χ(Kₙ) = n.

Cycles

For cycle graphs Cₙ (vertices arranged in a closed loop):

  • Even cycles (n even): Alternate two colors around the cycle. χ(Cₙ) = 2
  • Odd cycles (n odd): Two colors create a conflict when you return to the start—adjacent vertices would need the same color. You need a third color. χ(Cₙ) = 3

Think of it like seating people around a table where neighbors must wear different colored shirts—odd numbers create one unavoidable clash.

Trees

A tree is a connected graph with no cycles. You can color trees with just two colors using a simple strategy: pick a root, color it with color 1, then alternate colors level-by-level as you move away from the root. Since trees are bipartite, χ(T) = 2 (or 1 for a single vertex).

Key Takeaway: Bipartite graphs and trees have χ = 2, complete graphs Kₙ have χ = n, even cycles have χ = 2, and odd cycles have χ = 3.