Skip to content
Tutorials Center
My learning

Topics

Lesson 19 of 36 ยท Coloring and Matching

Graph Coloring Basics

Learn what a proper graph coloring is, how the chromatic number is defined, how to test k-colorability with backtracking, and why bipartite graphs need only two colors.

Imagine you must assign radio frequencies to transmitters. Two transmitters that are close together interfere, so they need different frequencies. You want to use as few frequencies as possible. Draw each transmitter as a vertex, join two vertices when they interfere, and you have a graph where the question becomes: how few colors do we need so that no edge joins two vertices of the same color?

That question is graph coloring, one of the oldest and most useful problems in the field. It looks like a puzzle, but it hides a hard computational core and a surprising amount of structure. In this chapter you will learn the definitions, build a solver from scratch, and connect coloring to matching, scheduling and planarity.

Proper colorings and the chromatic number

A vertex coloring assigns a color to every vertex. It is proper when adjacent vertices always get different colors. A proper coloring that uses at most k colors is called a k-coloring, and a graph that has one is k-colorable.

The smallest k for which the graph is k-colorable is the chromatic number, written ฯ‡(G) ("chi of G"). Some quick facts you can check by hand:

Graph ฯ‡(G) Why
Empty graph (no edges) 1 Nothing conflicts
Complete graph Kn n Every pair is adjacent
Path with 2 or more vertices 2 Alternate colors
Even cycle C2k 2 Alternate colors
Odd cycle C2k+1 3 Alternating fails at the last edge
Star K1,n 2 Center one color, leaves the other

Notice the pattern: a graph is 1-colorable exactly when it has no edges, and (as you will see below) 2-colorable exactly when it has no odd cycle.

What is a proper coloring?

Colors One per vertex
Edges Join conflicting vertices
Rule Ends of an edge differ

Proper means no edge is monochromatic

1 / 2

Lower bounds: cliques

A clique is a set of vertices that are all pairwise adjacent. Every vertex of a clique of size k needs its own color, so ฯ‡(G) โ‰ฅ ฯ‰(G), where ฯ‰(G) is the size of the largest clique. This bound is not always tight. The famous Mycielski construction builds triangle-free graphs (ฯ‰ = 2) with arbitrarily large chromatic number, so having no big clique does not mean few colors.

flowchart LR
    A((A)) --- B((B))
    B --- C((C))
    C --- A
    C --- D((D))
    D --- E((E))
    E --- C

Two triangles sharing the vertex C (a "bowtie"). The largest clique has 3 vertices, so at least 3 colors are needed; and 3 are enough.

Testing k-colorability with backtracking

Deciding whether a graph is 3-colorable is NP-complete, so no fast general algorithm is known. For small graphs, backtracking works well: color vertices one at a time, try each color that does not conflict with already-colored neighbors, and undo the choice if you get stuck.

Python Backtracking k-coloring and the chromatic number

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The solver tries k = 1, 2, 3, โ€ฆ and returns the first k that works, which is by definition ฯ‡(G). Ordering vertices by degree is a cheap heuristic: crowded vertices are the most constrained, so failing early prunes more of the search tree.

Bipartite graphs: the 2-colorable case

A graph is bipartite when its vertices can be split into two sets so that every edge goes between the sets. That is exactly the same as being 2-colorable: call the sets "red" and "blue". A classical theorem says a graph is bipartite if and only if it contains no odd cycle.

You can test this in linear time with breadth-first search: color the start vertex 0, give every neighbor the opposite color, and report failure the moment an edge joins two vertices with equal colors. That failing edge closes an odd cycle.

Python Bipartite test with BFS (and an odd cycle witness)

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Grids are bipartite because moving one step always flips the parity of row + column, which is precisely the checkerboard coloring.

Coloring is a labeling of independent sets

Another way to see a k-coloring: the vertices of each color form an independent set (no two are adjacent). So a k-coloring is a partition of the vertex set into k independent sets, and ฯ‡(G) is the smallest number of independent sets that cover the graph. This view explains why coloring models scheduling so well: each color class is a group of tasks that may run at the same time. You will build that application in scheduling and timetabling.

Common mistakes

  • Confusing ฯ‡(G) with the number of colors a particular algorithm used. A heuristic only gives an upper bound.
  • Assuming a graph with no triangles is 2-colorable. Odd cycles of length 5, 7, โ€ฆ and Mycielski graphs break that.
  • Forgetting disconnected graphs: you must color every component. The chromatic number is the maximum over components.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What is the chromatic number of the complete graph K5?

    Every pair of vertices in K5 is adjacent, so all five need different colors.
  2. 2. Which graphs are exactly the 2-colorable ones?

    A graph is bipartite (2-colorable) if and only if it has no odd cycle. Even cycles and trees are bipartite, but so are many other graphs.
  3. 3. A graph contains a clique of size 4. What can you conclude?

    The four clique vertices need four distinct colors, so ฯ‡(G) โ‰ฅ 4. The graph might need more colors elsewhere.
  4. 4. What does the BFS 2-coloring test report when it meets an edge whose ends have the same color?

    Same-colored ends of an edge together with the BFS tree paths form an odd cycle. The graph is therefore not bipartite (it may still need more than three colors).

Summary

  • A proper coloring gives adjacent vertices different colors; ฯ‡(G) is the fewest colors possible.
  • Cliques give lower bounds: ฯ‡(G) โ‰ฅ ฯ‰(G), but the gap can be large.
  • Deciding k-colorability is NP-complete for k โ‰ฅ 3; backtracking works for small graphs.
  • 2-colorable means bipartite means no odd cycle, and BFS tests it in linear time.
  • Each color class is an independent set, which is why coloring models scheduling.

Next: Greedy Coloring and Brooks' Theorem