From an Elimination Ordering to a Coloring
A chordal graph can be supplied with an ordering of its vertices that records useful structure: when a vertex is removed, all of its remaining neighbors are pairwise adjacent. This structure gives two outputs at once. Processing the ordering in reverse lets us color each vertex while seeing a clique of already-colored neighbors; examining the same sets also lets us extract a maximum clique.
All graphs in this tutorial are finite and simple. A clique is a set of pairwise adjacent vertices. A proper coloring assigns colors to vertices so that adjacent vertices receive different colors. The chromatic number \(\chi(G)\) is the minimum number of colors in a proper coloring. The clique number \(\omega(G)\) is the largest size of a clique. A maximum clique has size \(\omega(G)\); a maximal clique is one that cannot be enlarged, and need not be maximum.
A graph is chordal if it has no induced cycle of length at least four. The earlier characterization of chordal graphs by perfect elimination states that every chordal graph has a PEO. Here the ordering is given as part of the input. The algorithm below uses it; finding or recognizing such an ordering is a separate task.
The Algorithm
The two operations use the same sets \(N^+(v_i)\). Each \(C_i\) is a clique by the PEO condition, so it is a candidate clique. In the coloring pass, when \(v_i\) is reached, its already-colored neighbors are exactly \(N^+(v_i)\). Those neighbors form a clique, and therefore have distinct colors. The algorithm chooses a color not among them.
Worked Example: Coloring and Extracting a Clique
Let \(G\) have \(V=\{1,2,3,4,5\}\) and \(E=\{12,13,23,24,34,45\}\), and take the ordering \(1,2,3,4,5\). The later-neighbor sets are \(N^+(1)=\{2,3\}\), \(N^+(2)=\{3,4\}\), \(N^+(3)=\{4\}\), \(N^+(4)=\{5\}\), and \(N^+(5)=\varnothing\). The first two sets are cliques because \(23\in E\) and \(34\in E\); the remaining sets, with at most one vertex, are cliques. This is a PEO.
Coloring in reverse order gives the following trace. The “forbidden colors” are those already used by later neighbors.
| Vertex processed | Later neighbors and their colors | Forbidden colors | Assigned color |
|---|---|---|---|
| 5 | None | None | 1 |
| 4 | 5: 1 | 1 | 2 |
| 3 | 4: 2 | 2 | 1 |
| 2 | 3: 1, 4: 2 | 1, 2 | 3 |
| 1 | 2: 3, 3: 1 | 1, 3 | 2 |
Thus the colors of \(1,2,3,4,5\) are \(2,3,1,2,1\), respectively. The candidate cliques are \(C_1=\{1,2,3\}\), \(C_2=\{2,3,4\}\), \(C_3=\{3,4\}\), \(C_4=\{4,5\}\), and \(C_5=\{5\}\). A largest candidate is \(C_2=\{2,3,4\}\), of size \(3\).
Check: For edges \(12,13,23,24,34,45\), the endpoint colors are, respectively, \(2,3\); \(2,1\); \(3,1\); \(3,2\); \(1,2\); and \(2,1\). Every edge has differently colored endpoints. Also, \(2,3,4\) are pairwise adjacent, so any proper coloring needs at least three colors. The displayed coloring uses three, confirming it is optimal.
Why the Clique Candidates Find a Maximum
Proof. Each \(C_i=\{v_i\}\cup N^+(v_i)\) is a clique: the later neighbors are pairwise adjacent by the PEO condition, and each is adjacent to \(v_i\) by definition. Hence \(|C_i|\le\omega(G)\) for every \(i\), so \(\max_i|C_i|\le\omega(G)\). Conversely, choose a maximum clique \(K\), and let \(v_i\) be its vertex with smallest index in the ordering. Every other vertex of \(K\) occurs later than \(v_i\) and is adjacent to \(v_i\). Thus \(K\subseteq C_i\), so \(\omega(G)=|K|\le |C_i|\le\max_j|C_j|\). The two inequalities give the claimed equality. \(\square\)
This argument proves more than that each candidate is a clique: it shows that some candidate contains every maximum clique. Selecting a largest \(C_i\) therefore returns a maximum clique, not merely a maximal one.
Correctness and Optimality of the Coloring
Proof. The empty graph has no vertices, edges, or nonempty cliques; by the stated convention its empty clique has size zero, and no colors are needed. Now suppose \(G\) is nonempty. At the moment \(v_i\) is colored, the vertices already processed are precisely \(v_j\) with \(j>i\). Therefore its already-colored neighbors are precisely \(N^+(v_i)\). The algorithm selects a color not used by any of them. Every edge joins a vertex to a neighbor, and its earlier endpoint is colored after its later endpoint. When that earlier endpoint is processed, the later endpoint’s color is forbidden. Consequently every edge has endpoints of different colors, and the coloring is proper.
The colors on \(N^+(v_i)\) are all distinct, because \(N^+(v_i)\) is a clique and the coloring already assigned to those vertices is proper. If \(d_i=|N^+(v_i)|\), there are \(d_i\) distinct forbidden colors, so among the first \(d_i+1\) positive colors at least one is available. The color assigned to \(v_i\) is consequently at most \(d_i+1=|C_i|\le\omega(G)\), where the final inequality holds because \(C_i\) is a clique. Thus the algorithm uses at most \(\omega(G)\) colors.
On the other hand, the proposition gives a clique of size \(\omega(G)\). In any proper coloring, its vertices must all have distinct colors, so every proper coloring uses at least \(\omega(G)\) colors. The algorithm’s proper coloring therefore uses exactly \(\omega(G)\) colors and is optimal. The proposition also proves that the clique extraction returns a maximum clique. \(\square\)
Running Time
Assume the graph is represented by adjacency lists and the PEO is supplied as a list. The vertex indices let the algorithm identify which neighbors occur later. The running time is \(O(n+m)\), where \(n=|V(G)|\) and \(m=|E(G)|\).
To implement smallest-available-color selection efficiently, use an array of color marks and a fresh timestamp for each vertex being processed. Scan its adjacency list and mark the colors of its already-colored neighbors with that timestamp. Then test colors \(1,2,\dots\) in order until reaching one not marked with the current timestamp. No clearing of the whole array is needed between vertices. If \(d_i=|N^+(v_i)|\), at most \(d_i\) distinct colors are marked, so the search tests at most \(d_i+1\) colors.
Each edge contributes once to \(\sum_i d_i\), at its endpoint that occurs earlier in the PEO. Hence \(\sum_i d_i=m\). Scanning all adjacency lists takes \(2m\) edge examinations; the color searches take at most \(\sum_i(d_i+1)=m+n\) tests. The total is therefore \(O(n+m)\). To extract the largest candidate, scan each vertex’s adjacency list and count its later neighbors, keeping an index for a largest count. This costs \(O(n+m)\); one additional scan of the selected vertex’s adjacency list lists the clique. The algorithm uses \(O(n)\) extra storage for indices, colors, and marks, in addition to the graph representation.
Further Examples and a Common Pitfall
Worked Example: Disconnected Components and an Isolated Vertex
Let \(G\) have \(V=\{a,b,c,d,e,f\}\) and \(E=\{ab,bc,ac,de\}\). The vertices \(a,b,c\) form a triangle, \(d,e\) form a separate edge, and \(f\) is isolated. Use the ordering \(a,b,c,d,e,f\). The later-neighbor sets are \(\{b,c\}\), \(\{c\}\), \(\varnothing\), \(\{e\}\), \(\varnothing\), and \(\varnothing\), in that order. Each is a clique, so this is a PEO.
In reverse order, \(f\) receives color 1; \(e\) has no colored neighbor and receives color 1; \(d\), adjacent to \(e\), receives color 2; \(c\) receives color 1; \(b\), adjacent among later vertices only to \(c\), receives color 2; and \(a\), adjacent to \(b\) and \(c\), receives color 3. Thus the colors in the order \(a,b,c,d,e,f\) are \(3,2,1,2,1,1\). The candidates have sizes \(3,2,1,2,1,1\), so the first candidate \(\{a,b,c\}\) is a maximum clique.
Check: The edge colors on \(ab,bc,ac,de\) are \(3,2\); \(2,1\); \(3,1\); and \(2,1\), so the coloring is proper. The triangle requires three colors, and the algorithm uses three. The isolated vertex requires no new color.
Worked Example: Why the PEO Must Be Processed in Reverse
Let \(G\) have \(V=\{1,2,3,4\}\) and \(E=\{12,23,34\}\), and use the ordering \(1,4,2,3\). The later-neighbor sets in that order are \(\{2\}\), \(\{3\}\), \(\{3\}\), and \(\varnothing\). They are all cliques, so this is a PEO.
If one incorrectly colors in the listed order, vertex \(1\) receives color 1, vertex \(4\) receives color 1, vertex \(2\) receives color 2 because it is adjacent to \(1\), and vertex \(3\) receives color 3 because its neighbors \(2\) and \(4\) have colors 2 and 1. The forward pass uses three colors, even though the graph is a path.
In the required reverse order \(3,2,4,1\), vertex \(3\) receives color 1; vertex \(2\) receives color 2; vertex \(4\), adjacent to \(3\), receives color 2; and vertex \(1\), adjacent to \(2\), receives color 1. This is a proper two-coloring. The edge endpoint colors are \(1,2\) on \(12\), \(2,1\) on \(23\), and \(1,2\) on \(34\). Since the graph has an edge, at least two colors are needed, so this coloring is optimal.
Common mistake: A PEO does not guarantee that greedy coloring in the PEO’s listed direction is optimal. The proof relies on the already-colored neighbors being exactly the later neighbors, which is true when processing in reverse. The forward calculation above fails for precisely that reason.
Check Your Understanding
Use the definitions and proof above to answer the following questions.
- For a PEO \(v_1,\dots,v_n\), explain why the already-colored neighbors of \(v_i\) are exactly \(N^+(v_i)\) when vertices are processed in reverse.
- Why does a largest set \(C_i=\{v_i\}\cup N^+(v_i)\) have size \(\omega(G)\), rather than merely being a maximal clique?
- Give a PEO for the graph with \(V=\{1,2,3,4\}\) and \(E=\{12,13,23,34\}\). Apply reverse greedy coloring and identify a maximum clique.
- Explain why the total number of color-search tests is at most \(m+n\) in the running-time analysis.
- What output should the algorithm give for an empty graph, and why does the nonempty-graph coloring argument need a separate case?