EP06

EP06: Graph Coloring and Voice Assignment

完美图, χ=ω

▶ 6:28 Graph TheoryCombinatorics

前置知识

EP03 Bach and Graph Connectivity EP04 All-Interval Rows and ℤ₁₂ EP05 Turán's Theorem and Counterpoint

小红书 Watch on 小红书

Overview

Beethoven’s Fifth Symphony, fourth movement, deploys over twenty orchestral staves. Collapse all octave doublings, and the climax still demands more than ten distinct pitch heights simultaneously — more than two human hands can play. How do you reduce a full orchestra to a piano score without destroying the harmonic structure? And what is the minimum number of voices absolutely required?

This episode answers both questions with graph coloring. Model each note as a vertex; connect two vertices when their sounding intervals overlap in time. The resulting interval graph encodes all simultaneity conflicts. The chromatic number $\chi(G)$ of this graph is the minimum number of voices (colors) needed so that no two simultaneously-sounding notes share a voice. The Perfect Graph Theorem (Lovász, 1972) guarantees that for interval graphs $\chi = \omega$ — the chromatic number equals the clique number, i.e., the maximum number of notes sounding at once. A single greedy pass along the time axis achieves this bound in linear time.

When $\omega$ exceeds the number of available performers, the theorem gives the precise cost of every forced deletion — turning an artistic choice into a quantifiable trade-off.

中文: “完美图定理给了我们一个保证：对区间图，χ永远等于ω。不多不少。”

Prerequisites

Graph Connectivity and Cut Vertices (EP03) — basic graph vocabulary: degree, path, cycle, connectivity
All-Interval Rows and $\mathbb{Z}_{12}$ (EP04) — group-theoretic thinking about music structure
Turán's Theorem (EP05) — cliques, extremal graph density

Definitions

Def 6.1 (Proper Graph Coloring)

A proper $k$ -coloring of a graph $G = (V,E)$ is a function $c : V \to \{1,2,\ldots,k\}$ such that $c(u) \ne c(v)$ whenever $\{u,v\} \in E$ .

The chromatic number $\chi(G)$ is the smallest $k$ for which a proper $k$ -coloring exists.

Def 6.2 (Clique Number)

A clique in $G$ is a set of vertices that are pairwise adjacent. The clique number $\omega(G)$ is the size of the largest clique.

Since any clique requires all its vertices to have distinct colors, $\chi(G) \ge \omega(G)$ always.

Def 6.3 (Interval Graph)

An interval graph $G = (V,E)$ is constructed from a finite set of closed intervals $\{[a_i, b_i]\}_{i=1}^n$ on the real line by:

setting $V = \{1, 2, \ldots, n\}$ (one vertex per interval),
connecting $i$ and $j$ with an edge iff $[a_i, b_i] \cap [a_j, b_j] \ne \emptyset$ (intervals overlap).

In the musical application, each interval $[a_i, b_i]$ represents the sounding duration of note $i$ : onset $a_i$ , release $b_i$ .

Def 6.4 (Perfect Graph)

A graph $G$ is perfect if for every induced subgraph $H \subseteq G$ :

\chi(H) = \omega(H).

Equivalently, $G$ is perfect iff neither $G$ nor its complement $\bar{G}$ contains an odd cycle of length $\ge 5$ as an induced subgraph (this is the content of the Strong Perfect Graph Theorem, Chudnovsky et al. 2006).

Def 6.5 (Chromatic Polynomial)

The chromatic polynomial $P(G, k)$ counts the number of proper $k$ -colorings of $G$ . It is a polynomial in $k$ of degree $|V|$ .

Examples:

$P(K_n, k) = k(k-1)(k-2)\cdots(k-n+1)$ — must assign $n$ distinct colors.
$P(T_n, k) = k(k-1)^{n-1}$ — tree on $n$ vertices; each new vertex has one neighbor constraint.
$P(C_5, k) = (k-1)^5 + (k-1)$ — the 5-cycle (odd cycle), which violates perfection: $P(C_5, 2) = 0$ but $\omega(C_5) = 2$ , confirming $\chi(C_5) = 3 > 2 = \omega(C_5)$ .

Main Theorems

Theorem 6.1 (Interval Graphs are Perfect)

Every interval graph is a perfect graph:

\chi(G) = \omega(G)

for any interval graph

G

Proof.

We show that the greedy algorithm achieves $\omega(G)$ colors, establishing $\chi(G) \le \omega(G)$ . Since $\chi \ge \omega$ always, equality follows.

Algorithm: Sort the $n$ intervals by left endpoint: $a_{\sigma(1)} \le a_{\sigma(2)} \le \cdots \le a_{\sigma(n)}$ . Process vertices in this order. When processing vertex $v$ with interval $[a_v, b_v]$ , assign the smallest color $c \notin \{c(u) : u \text{ is a neighbor of } v \text{ already processed}\}$ .

Claim: The algorithm uses at most $\omega(G)$ colors.

At the moment vertex $v$ is processed, the set of already-processed neighbors of $v$ is exactly $N_<(v) = \{u : a_u \le a_v \text{ and } b_u \ge a_v\}$ — the intervals that started before $v$ and are still sounding when $v$ begins. Together with $v$ itself, the set $N_<(v) \cup \{v\}$ is a clique (all pairwise overlapping, since they all contain $a_v$ in their interiors). Therefore $|N_<(v) \cup \{v\}| \le \omega(G)$ .

Since $v$ needs a color different from at most $|N_<(v)| = \omega(G) - 1$ colors, there is always a color in $\{1,\ldots,\omega(G)\}$ available. The algorithm never needs a $(\omega(G)+1)$ -th color. $\square$

Why general graphs fail: The odd 5-cycle $C_5$ has $\omega = 2$ but $\chi = 3$ . The greedy ordering can be bad (e.g., alternating vertices of $C_5$ ) and need a third color. But $C_5$ cannot be an interval graph, because any five intervals containing a cyclic overlap pattern must contain a “triangle” (three mutually overlapping intervals) by the Helly property for intervals on the line: if pairwise intersections are nonempty, the total intersection is nonempty.

Theorem 6.2 (Perfect Graph Theorem (Lovász, 1972))

A graph $G$ is perfect if and only if its complement $\bar{G}$ is perfect.

Equivalently (the Weak Perfect Graph Theorem): $G$ is perfect iff it contains no odd cycle of length $\ge 5$ as an induced subgraph, and neither does $\bar{G}$ .

Proof.

The full proof is deep (Lovász’s original 1972 proof uses a topological argument; the full Strong Perfect Graph Theorem by Chudnovsky, Robertson, Seymour, Thomas (2006) is a 150-page paper). We give the key idea for the weak version.

Necessity ( $\Rightarrow$ ): An odd cycle $C_{2k+1}$ with $k \ge 2$ has $\omega = 2$ (no triangle since it is an odd cycle) but $\chi = 3$ (it takes 3 colors to properly color any odd cycle). So it is not perfect.

Sufficiency ( $\Leftarrow$ ) sketch (Lovász’s approach): The key lemma is that any minimal non-perfect graph $G$ must satisfy $|V||E(\bar{G})| \ge \binom{|V|}{2} + \alpha(G)\omega(G)$ where $\alpha$ is the independence number. Lovász showed this forces the existence of an odd hole or odd antihole. The details require the theory of perfect graph structure theorems. $\square$

Theorem 6.3 (Brooks' Theorem)

For any connected graph $G$ that is neither a complete graph $K_n$ nor an odd cycle $C_{2k+1}$ :

\chi(G) \le \Delta(G)

where

\Delta(G)

is the maximum degree.

(The bound $\chi(G) \le \Delta(G) + 1$ always holds by greedy coloring; Brooks' theorem improves this by 1 in all non-exceptional cases.)

Proof.

Greedy bound $\chi \le \Delta + 1$ : When the greedy algorithm processes a vertex $v$ , it has at most $\deg(v) \le \Delta$ neighbors already colored. At most $\Delta$ colors are forbidden, so one of $\{1, \ldots, \Delta+1\}$ is always available.

Improvement to $\Delta$ (sketch): The key step is to find a vertex ordering in which every vertex except the last has a neighbor later in the ordering. For a $\Delta$ -regular connected non-complete graph, one shows (using a spanning tree rooted at a non-cut vertex) an ordering where each vertex has at most $\Delta - 1$ earlier-colored neighbors, allowing greedy to use only $\Delta$ colors. The odd cycle is exceptional because any $\Delta = 2$ coloring attempt on $C_{2k+1}$ fails at the last step. $\square$

Prop 6.1 (Helly Property for Intervals)

Let

\{[a_i, b_i]\}_{i=1}^n

be a collection of intervals on the real line. If every two intervals intersect (pairwise intersection), then all intervals share a common point:

\bigcap_{i=1}^n [a_i, b_i] \ne \emptyset

Proof.

Let $p = \max_i a_i$ (rightmost left endpoint) and $q = \min_i b_i$ (leftmost right endpoint). For the interval achieving $p$ , say $[a_k, b_k]$ , and the interval achieving $q$ , say $[a_l, b_l]$ : since these two intersect, $a_k \le b_l$ , i.e., $p \le q$ . Then the point $p$ (or any point in $[p,q]$ ) belongs to every interval. $\square$

This property underlies the perfection of interval graphs: it prevents the formation of odd holes (chordless odd cycles of length $\ge 5$ ), since three pairwise-overlapping intervals always share a common time point, forming a triangle rather than a triangle-free cycle.

Musical Connection

音乐联系

Voice allocation as graph coloring

Every polyphonic score implicitly defines an interval graph: notes are vertices, simultaneous notes are adjacent. The chromatic number is the minimum voice count. For Bach’s C-major Fugue BWV 846:

Maximum simultaneous voices: $\omega = 4$
Chromatic number (by perfection): $\chi = 4$
Bach’s actual voices: 4 — exactly matching the theoretical minimum

No voice is redundant; no voice can be removed without a collision. The theorem proves that Bach’s four-voice writing is tight.

For Beethoven’s Fifth Symphony, fourth movement:

After collapsing octave doublings, $\omega > 10$ at the climax
Two hands give at most 10 simultaneous notes
The theorem guarantees the reduction is lossy by necessity, not by artistic choice

Liszt’s strategy (1865) as high-degree-first deletion

When $\omega > 10$ , Liszt retained the outer voices (melody and bass) and deleted middle-register doublings. In graph-theoretic terms: middle-register notes have the highest degree (most overlaps with other notes), so deleting them disrupts the fewest colorings. This is equivalent to a maximum independent set heuristic on the conflict subgraph — preserve as many non-conflicting notes as possible.

Register allocation in compilers (Chaitin, 1982)

IBM’s Gregory Chaitin recognized that assigning variables to CPU registers is exactly graph coloring: variables are vertices, two variables are adjacent if they are live simultaneously (overlap in program execution time), and registers are colors. The variable liveness graph is an interval graph (live ranges are intervals of program time), so $\chi = \omega$ and greedy allocation is optimal when registers suffice. When registers are insufficient ( $\omega > k$ registers available), some variables must “spill” to memory. Chaitin’s heuristic: spill the variable with the highest degree (most conflicts) — the same principle as Liszt deleting the most-overlapping middle voices.

Music and compiler design, separated by 117 years, converge on the same graph-coloring trade-off.

Limits and Open Questions

The Four Color Theorem. For planar graphs (graphs drawable without edge crossings), $\chi \le 4$ . Proved by Appel and Haken (1976) using computer-assisted case analysis — the first major theorem proved by computer. Musical planar graphs arise when voice crossings are forbidden (a common constraint in choral writing).
Kempe chains and the failed 1879 proof. Alfred Kempe published a purported proof of the four color theorem in 1879. His key idea was “Kempe chains” — maximal connected subgraphs alternating between two colors. In 1890, Percy Heawood found Kempe’s proof was flawed. Kempe chains are still used in graph coloring algorithms; the flaw only appears in a subtle case with five-colored maps.
Chromatic polynomial complexity. Computing $P(G, k)$ for general $G$ is $\#\mathbf{P}$ -hard (harder than NP), but for interval graphs it can be computed in polynomial time due to the perfect structure.
Tonal pitch space vs. pitch height. The interval graph model treats pitch height as a continuous real variable. But Western tonal harmony groups notes into equivalence classes (e.g., C4 and C5 are “the same harmony”). A richer model uses the pitch helix (introduced in EP08) and asks about coloring in that quotient space.
Weighted coloring for dynamics. If different notes carry different dynamic markings, a weighted chromatic number would give the minimum number of weighted voices. This is open in general for weighted interval graphs.

Academic References

Lovász, L. (1972). Normal hypergraphs and the perfect graph conjecture. Discrete Mathematics, 2(3), 253–267.
Chudnovsky, M., Robertson, N., Seymour, P., & Thomas, R. (2006). The strong perfect graph theorem. Annals of Mathematics, 164(1), 51–229.
Golumbic, M. C. (2004). Algorithmic Graph Theory and Perfect Graphs (2nd ed.). Elsevier. (The standard reference on interval graphs and perfect graphs.)
Brooks, R. L. (1941). On colouring the nodes of a network. Mathematical Proceedings of the Cambridge Philosophical Society, 37(2), 194–197.
Chaitin, G. J. (1982). Register allocation and spilling via graph coloring. ACM SIGPLAN Notices, 17(6), 98–105.
Appel, K., & Haken, W. (1977). Every planar map is four colorable. Bulletin of the American Mathematical Society, 82(5), 711–712.
Tymoczko, D. (2011). A Geometry of Music. Oxford University Press. Ch. 3 (Voice leading as motion in chord space).
West, D. B. (2001). Introduction to Graph Theory (2nd ed.). Prentice Hall. Ch. 5 (Graph coloring).