Skip to content
Tutorials Center
My learning

Topics

Lesson 21 of 36 Β· Coloring and Matching

Edge Coloring and the Chromatic Polynomial

Color the edges of a graph, learn Vizing's theorem and Konig's edge coloring theorem, and count proper colorings with the chromatic polynomial and deletion-contraction.

So far we colored vertices. You can just as well color edges so that edges sharing an endpoint get different colors. This models problems like scheduling a round-robin tournament (each match is an edge, each round is a color, and a player cannot play twice in one round). A second question is not "how few colors?" but "how many proper colorings exist with k colors?". The answer is a polynomial in k, the chromatic polynomial.

Edge coloring and the chromatic index

A proper edge coloring gives different colors to any two edges that share a vertex. The smallest number of colors needed is the chromatic index Ο‡'(G). Each color class is a set of pairwise non-touching edges, that is, a matching. So an edge coloring is a partition of the edges into matchings.

Two bounds are immediate. A vertex of maximum degree Ξ” has Ξ” edges that all need different colors, so Ο‡'(G) β‰₯ Ξ”. And Vizing's theorem gives a sharp upper bound for simple graphs:

Ξ”(G) ≀ Ο‡'(G) ≀ Ξ”(G) + 1.

Graphs therefore fall into just two classes: Class 1 (Ο‡' = Ξ”) and Class 2 (Ο‡' = Ξ” + 1). Deciding which class a graph belongs to is NP-complete in general, but for bipartite graphs it is easy: KΓΆnig's edge-coloring theorem says every bipartite graph is Class 1.

An edge coloring of G is exactly a vertex coloring of its line graph L(G), which has one vertex per edge of G and joins two vertices when the edges share an endpoint. That lets us reuse our vertex-coloring solver.

Python Chromatic index through the line 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.

K4 is Class 1 (three perfect matchings), K5 is Class 2 (every vertex has degree 4, yet 5 colors are needed because a color class can hold at most 2 edges and K5 has 10 edges). In general a complete graph Kn has Ο‡' = n - 1 for even n and n for odd n. The even case is the classic round-robin schedule.

Round-robin tournaments

For n teams (even), the "circle method" fixes one team and rotates the others; each rotation is a perfect matching and one color. It builds an explicit (n-1)-edge-coloring of Kn.

Python Circle method: edge coloring K_n for a round-robin

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.

Counting colorings: the chromatic polynomial

Let P(G, k) be the number of proper vertex colorings of G using colors from a set of k colors (not all colors need to appear). Examples you can derive directly:

  • Empty graph on n vertices: k^n.
  • Path or any tree on n vertices: k(k-1)^(n-1), because after the first vertex each new vertex avoids exactly its parent's color.
  • Complete graph Kn: k(k-1)(k-2)Β·Β·Β·(k-n+1).
  • Cycle Cn: (k-1)^n + (-1)^n (k-1).

For general graphs use deletion-contraction. For any edge e = uv:

P(G, k) = P(G βˆ’ e, k) βˆ’ P(G / e, k)

G βˆ’ e deletes the edge, and G / e merges u and v into one vertex. Colorings of G βˆ’ e either give u and v different colors (those are proper colorings of G) or the same color (those correspond to colorings of G / e). The recursion bottoms out at graphs with no edges, whose polynomial is k^n.

Python Chromatic polynomial by deletion-contraction

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 triangle gives k^3 βˆ’ 3k^2 + 2k = k(kβˆ’1)(kβˆ’2), matching the complete-graph formula. Because P(G, k) counts colorings, the chromatic number is the smallest positive integer k with P(G, k) > 0.

What the coefficients reveal

  • The degree equals the number of vertices n, and the leading coefficient is 1.
  • The coefficient of k^(n-1) is βˆ’m, where m is the number of edges.
  • The coefficients alternate in sign, and the polynomial has no constant term (P(G, 0) = 0).
  • The number of connected components equals the multiplicity of the root k = 0.
  • P(G, 1) = 0 whenever the graph has an edge, so the factor (k βˆ’ 1) appears for every connected graph with at least one edge.

Another beautiful fact: evaluating |P(G, βˆ’1)| counts the acyclic orientations of the graph (Stanley's theorem). The triangle has |P(βˆ’1)| = 6: each of the 3! linear orders of the vertices gives a distinct acyclic orientation.

flowchart TD
    G["P(G, k)"] --> D["P(G βˆ’ e, k)"]
    G --> C["βˆ’ P(G / e, k)"]
    D --> D1["... fewer edges"]
    C --> C1["... fewer vertices"]
    D1 --> L["k^n at the leaves"]
    C1 --> L

Each deletion-contraction step produces two smaller graphs, so the recursion is exponential in general.

Check your understanding

Quick check Β· 4 questions

of 4 answered You scored / 4 Β· perfect!

  1. 1. Which statement is Vizing's theorem for a simple graph?

    Vizing proved that edge colorings need either Ξ” or Ξ” + 1 colors, which splits graphs into Class 1 and Class 2.
  2. 2. Every bipartite graph is Class 1. What is its chromatic index?

    KΓΆnig's edge-coloring theorem states that bipartite graphs have Ο‡' = Ξ”.
  3. 3. What is the chromatic polynomial of a tree on n vertices?

    The first vertex has k choices and each later vertex avoids only its parent's color, giving k - 1 choices.
  4. 4. In deletion-contraction, what does P(G / e, k) count?

    Contracting e merges its endpoints, so its colorings correspond to colorings of G βˆ’ e that give u and v one common color. Subtracting them leaves the proper colorings of G.

Summary

  • A proper edge coloring partitions edges into matchings; the minimum number is the chromatic index Ο‡'(G).
  • Vizing: Ξ” ≀ Ο‡' ≀ Ξ” + 1; bipartite graphs always have Ο‡' = Ξ” (KΓΆnig).
  • Edge colorings of G are vertex colorings of the line graph; Kn needs n βˆ’ 1 rounds for even n and n for odd n.
  • The chromatic polynomial P(G, k) counts proper k-colorings and obeys P(G) = P(G βˆ’ e) βˆ’ P(G / e).
  • Its coefficients encode vertices, edges and components, and Ο‡(G) is the smallest k with P(G, k) > 0.

Next: Bipartite Matching