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 χ(G)\chi(G) 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 χ(G)\chi(G) is the fewest time slots.

Exam conflicts colored with three time slots Five vertices M, P, C, B and E around a pentagon, M–P–C–B–E–M, with one more edge from M to C. M and B share the first color, P and E the second, and C the third. The triangle M, P, C forces three colors. M P C B E
Exam conflicts colored with three 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 χ≤2\chi \le 2 are called bipartite.

Bounds on χ

  • A complete subgraph KrK_r inside GG forces χ(G)≥r\chi(G) \ge r, 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 Δ\Delta, at most Δ\Delta colors are blocked, so χ(G)≤Δ+1\chi(G) \le \Delta + 1.
  • Every planar graph has χ≤4\chi \le 4: the four color theorem.

Worked examples

Common mistakes

Practice problems

  1. Find χ(K6)\chi(K_6).

    Answer

    66

    Full solution

    All six vertices are neighbors, so all six colors must differ.

  2. Find χ(C8)\chi(C_8) and χ(C9)\chi(C_9).

    Answer

    22 and 33

    Full solution

    Even cycles alternate two colors; odd cycles need a third.

  3. What is the chromatic number of a tree with 1010 vertices?

    Answer

    22

    Full solution

    A tree has no cycles at all, so no odd cycles, and it has at least one edge.

  4. Find χ\chi for a wheel with a 66-vertex rim.

    Answer

    33

    Full solution

    The even rim takes 22 colors and the hub a third. A hub and two neighboring rim vertices form a triangle, so 22 is not enough.

  5. Every vertex of a graph has degree at most 44. What does greedy coloring guarantee?

    Answer

    At most 55 colors

    Full solution

    χ≤Δ+1=5\chi \le \Delta + 1 = 5.

  6. Is a 55-cycle bipartite?

    Answer

    No

    Full solution

    It is an odd cycle, so it needs 33 colors.

  7. 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

    22

    Full solution

    The conflict graph is the 44-cycle A–B–C–D–A, so A and C meet at one time and B and D at another.

  8. A student colors a graph greedily, uses 44 colors, and concludes χ=4\chi = 4. What is wrong?

    Answer

    Greedy coloring gives only an upper bound; χ\chi may be smaller.

    Full solution

    A different order may use fewer colors. To prove χ=4\chi = 4, the student needs a reason 33 colors fail, such as a K4K_4 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.