Skip to content
Tutorials Center
My learning

Topics

Lesson 48 of 68 ยท Graph Theory

Graph Coloring and Planarity

Learn chromatic numbers, greedy and exact coloring, bipartite tests, scheduling as coloring, Euler's formula and planar graphs, with Python code.

Imagine scheduling exams so that no student has two at the same time, or assigning radio frequencies so that nearby towers do not interfere, or filling in a map so that neighboring countries get different colors. All three are the same problem in disguise: label the vertices of a graph so that adjacent vertices get different labels, using as few labels as possible. That is graph coloring.

The map-coloring version leads to the second half of the lesson, planar graphs: graphs that can be drawn on paper without crossing edges. Euler found a formula that links the vertices, edges and faces of such drawings, and it quickly shows that some small graphs cannot be drawn flat. We code the coloring parts and the edge-count tests, and discuss the famous Four Color Theorem as a read-only story.

Coloring in one picture

Proper coloring Adjacent vertices never share a color.
Chromatic number The fewest colors that work, written ฯ‡(G).
Scheduling Colors are time slots, edges are conflicts.
1 / 2

Proper colorings and the chromatic number

A proper coloring assigns a color to each vertex so that no edge has the same color at both ends. The chromatic number ฯ‡(G) is the smallest number of colors for which a proper coloring exists. A few values to remember:

  • An edgeless graph needs 1 color. Any graph with an edge needs at least 2.
  • The complete graph K_n needs n colors, since every pair is adjacent.
  • A path or any tree needs 2. An even cycle needs 2; an odd cycle needs 3.
  • Adding a vertex of degree d never forces more than d + 1 colors on its own, which gives the general bound ฯ‡(G) โ‰ค ฮ” + 1, where ฮ” is the largest degree.
  • A graph containing a copy of K_k needs at least k colors.

Bipartite graphs: 2-colorable graphs

A graph is bipartite when its vertices split into two groups with every edge crossing between the groups. That is the same as being 2-colorable. There is a neat characterization: a graph is bipartite exactly when it has no odd cycle. An odd cycle cannot be 2-colored since the colors would have to alternate around a loop of odd length.

The test is a BFS: color the start vertex 0, give its neighbors color 1, their neighbors color 0, and so on. If you ever meet an edge whose ends already have the same color, you have found an odd cycle, and the graph is not bipartite.

Python Testing bipartiteness with a two-coloring BFS

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.

Greedy coloring and why order matters

Finding ฯ‡(G) exactly is NP-hard for general graphs, but a fast greedy method gives a valid coloring: go through the vertices in some order and give each one the smallest color not used by its already-colored neighbors. Because a vertex has at most ฮ” neighbors, greedy never uses more than ฮ” + 1 colors.

Greedy is not always optimal, and the result depends on the order. A classic trap is the crown graph: take two groups a0..a3 and b0..b3 and join ai to bj whenever i โ‰  j. This graph is bipartite, so 2 colors suffice. Process the vertices in the order a0, b0, a1, b1, ... and greedy is lured into using 4. A popular heuristic is Welsh-Powell: process vertices by decreasing degree, so the most constrained vertices go first.

To get the exact answer on small graphs we can use backtracking: try to color with k colors, undoing the last choice whenever a vertex has no legal color, and increase k until it succeeds.

Python Greedy colorings versus the exact 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.

Scheduling as coloring

Build a conflict graph: one vertex per exam, an edge between two exams when some student takes both. A proper coloring is a timetable in which no student has a clash, and each color is a time slot. The chromatic number is the minimum number of slots needed. You will turn this into a full program in Project: Exam Scheduler with Graph Coloring.

Python Exam timetable from a conflict graph

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.

Planar graphs and Euler's formula

A graph is planar if it can be drawn in the plane with no two edges crossing. A particular crossing-free drawing divides the plane into faces, including the unbounded outer face. For a connected planar drawing with V vertices, E edges and F faces,

V - E + F = 2

You can see why by starting from a single vertex (V = 1, E = 0, F = 1, so the sum is 2) and growing the drawing: adding a new vertex with one edge raises V and E by 1, and closing a cycle with a new edge raises E and F by 1. Neither move changes the sum. For a graph with C components, the formula becomes V - E + F = 1 + C.

Euler's formula limits how many edges a planar graph can have. Every face is bounded by at least 3 edge-sides (for V โ‰ฅ 3), and each edge borders at most 2 faces, so 3F โ‰ค 2E. Substitute F = 2 - V + E and rearrange:

  • E โ‰ค 3V - 6 for any simple planar graph with V โ‰ฅ 3;
  • E โ‰ค 2V - 4 if the graph is also bipartite (every face has at least 4 sides).

These are tests for non-planarity: K5 has V = 5, E = 10, but 3ยท5 - 6 = 9, so K5 cannot be drawn flat. K_{3,3} has V = 6, E = 9, but the bipartite bound is 2ยท6 - 4 = 8, so it cannot be either. Kuratowski's theorem says these two graphs are the whole story: a graph is planar exactly when it contains no subdivision of K5 or K_{3,3}.

The bounds are necessary, not sufficient. The 10-vertex Petersen graph has 15 edges and slips under the 3V - 6 = 24 limit, yet it is not planar.

Python Edge-count tests for planarity and faces from Euler's formula

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.

For the cube, V - E + F = 2 gives F = 6: the six square faces. For the octahedron the formula gives 8 triangular faces.

The Four Color Theorem

Any map on a plane or sphere can be colored with at most four colors so that regions sharing a border get different colors. In graph terms: every planar graph has ฯ‡ โ‰ค 4. This was conjectured in 1852 and proved in 1976 by Appel and Haken, with a computer checking a large list of unavoidable configurations. It was the first major theorem proved with essential computer help, and the proof was controversial for that reason. Five colors have a short proof by hand. Four colors are sometimes really needed: K4 is planar and needs all four. You cannot reproduce the full proof in a lesson, but you can use the result: any planar conflict graph is guaranteed to fit into four time slots or four frequencies.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What is the chromatic number of an odd cycle such as C_7?

    Two colors would have to alternate around the cycle, which fails when the length is odd. Three colors always suffice.
  2. 2. A graph is bipartite exactly when it:

    Bipartite means 2-colorable, and an odd cycle cannot be 2-colored; conversely a graph with no odd cycle can be 2-colored by BFS.
  3. 3. The largest degree in a graph is 5. What does greedy coloring guarantee?

    A vertex has at most 5 neighbors, so among 6 colors at least one is free. Greedy can use up to Delta + 1 = 6 colors and may be non-optimal.
  4. 4. A connected planar drawing has 9 vertices and 14 edges. How many faces does it have, counting the outer face?

    From V - E + F = 2: F = 2 - 9 + 14 = 7.
  5. 5. Why is K5 not planar?

    The bound E <= 3V - 6 allows at most 9 edges for V = 5, but K5 has C(5,2) = 10.

Summary

  • A proper coloring gives adjacent vertices different colors; ฯ‡(G) is the fewest colors needed. ฯ‡(K_n) = n, odd cycles need 3, trees need 2, and ฯ‡ โ‰ค ฮ” + 1.
  • A graph is bipartite (2-colorable) exactly when it has no odd cycle; a BFS two-coloring tests this.
  • Greedy coloring is fast but order-dependent; exact coloring needs backtracking and is NP-hard in general.
  • Scheduling and frequency assignment are coloring problems on a conflict graph.
  • For connected planar drawings V - E + F = 2, so E โ‰ค 3V - 6 (and E โ‰ค 2V - 4 if bipartite); K5 and K_{3,3} are not planar.
  • The Four Color Theorem says every planar graph is 4-colorable.

Next: Shortest Paths, Matching and Flows, where edges carry weights and capacities.