From Elimination Orderings to Perfection
A chordal graph has a special ordering of its vertices: each vertex is simplicial among the vertices that follow it. This local condition has a direct coloring consequence. If we color in reverse order, then the already-colored neighbors of a vertex form a clique. Their number is therefore limited by the size of the largest clique, so a color remains available. The key point for perfection is that this argument works not only for the whole graph, but also for every induced subgraph.
All graphs in this tutorial are finite and simple. A set \(S\subseteq V(G)\) induces the graph \(G[S]\), whose vertices are \(S\) and whose edges are all edges of \(G\) with both endpoints in \(S\). A clique is a set of pairwise adjacent vertices. A proper vertex coloring assigns colors to vertices so that adjacent vertices receive different colors. The clique number \(\omega(G)\) is the largest size of a clique, and the chromatic number \(\chi(G)\) is the least number of colors in a proper coloring. We use \(\omega(G)=\chi(G)=0\) for the graph with no vertices.
The earlier material on the chordal graph characterization by perfect elimination establishes that a graph is chordal if and only if it has a PEO. We use that characterization here, rather than proving it again. The coloring argument below proves the implication that is needed: a PEO bounds the number of colors by the clique number.
Why the Ordering Restricts to Induced Subgraphs
Proof. Write the subsequence as \(u_1,\ldots,u_k\), in the order in which its vertices occur in \(v_1,\ldots,v_n\). Fix \(u_j=v_i\). Any neighbor of \(u_j\) in \(G[S]\) that occurs later in the subsequence is a neighbor of \(v_i\) that occurs later in the original ordering. By the PEO property in \(G\), all such later neighbors are pairwise adjacent in \(G\). Since they lie in \(S\), their edges also belong to the induced subgraph \(G[S]\). Thus the later neighbors of each \(u_j\) form a clique in \(G[S]\), as required. If \(S\) is empty, its empty ordering satisfies the definition vacuously. \(\square\)
There is also a direct chordal-graph explanation for why the argument applies to every induced subgraph. If \(G\) is chordal, then \(G[S]\) is chordal: an induced cycle of length at least four in \(G[S]\) would have exactly the same vertices and edges among them in \(G\), so it would be an induced cycle there as well. The chordal–PEO characterization therefore supplies an ordering for each \(G[S]\). The lemma gives the stronger conclusion that if we already have one PEO of \(G\), restricting it provides an ordering for every \(G[S]\).
The Coloring Bound and the Perfection Theorem
Proof. If \(G\) has no vertices, both parameters equal zero by convention. Otherwise, let \(v_1,\ldots,v_n\) be a PEO and put \(q=\omega(G)\). A one-vertex clique exists, so \(q\geq 1\). Color the vertices in reverse order, \(v_n,v_{n-1},\ldots,v_1\), using a palette of \(q\) colors.
When \(v_i\) is reached, its already-colored neighbors are precisely its neighbors among \(v_{i+1},\ldots,v_n\). These neighbors form a clique by the PEO property. If there are \(r\) such neighbors, then the \(r\) neighbors together with \(v_i\) form a clique in \(G\), so \(r+1\leq q\). In particular, at most \(q-1\) colors are used on those neighbors. At least one of the \(q\) colors is therefore available for \(v_i\). Assign such a color. For any edge, the endpoint colored later in this reverse process receives a color different from the endpoint already colored, because that already-colored endpoint is one of its neighbors. Thus the resulting coloring is proper and uses at most \(q\) colors, proving \(\chi(G)\leq\omega(G)\).
For the reverse inequality, take a clique of size \(q=\omega(G)\). Its \(q\) vertices are pairwise adjacent, so a proper coloring must assign them \(q\) different colors. Hence \(\chi(G)\geq\omega(G)\), and equality follows. Now suppose \(G\) is chordal. Each induced subgraph \(G[S]\) is chordal and therefore has a PEO by the chordal–PEO characterization. Applying the equality just proved to \(G[S]\) gives \(\chi(G[S])=\omega(G[S])\). This holds for every \(S\), including the empty set, so \(G\) is perfect. \(\square\)
The proof uses the ordering only to establish an upper bound on the number of colors. The clique gives the matching lower bound. For perfection, one must repeat this equality for every induced subgraph; having equality for the original graph alone would not suffice.
Worked Example: A Triangle with Two Pendant Vertices
Let \(G\) have vertex set \(V(G)=\{a,b,c,d,e\}\) and edge set \(E(G)=\{ab,ac,bc,ad,be\}\). Consider the ordering \(d,a,c,b,e\). The later neighbors of \(d\) are \(\{a\}\); those of \(a\) are \(\{b,c\}\), which are adjacent; those of \(c\) are \(\{b\}\); those of \(b\) are \(\{e\}\); and those of \(e\) are empty. Each set is a clique, so this is a PEO.
Color in reverse order \(e,b,c,a,d\), using three colors. Give \(e\) color 1. Since \(b\) is adjacent to \(e\), give \(b\) color 2. Since \(c\) is adjacent to \(b\), give \(c\) color 1. The vertex \(a\) is adjacent to both \(b\) and \(c\), which have colors 2 and 1, so give \(a\) color 3. Finally, \(d\) is adjacent only to \(a\), so give \(d\) color 1.
The triangle on \(\{a,b,c\}\) forces at least three colors. The coloring uses three, so \(\chi(G)=3\). No clique has more than three vertices: \(d\) has only one neighbor and \(e\) has only one neighbor, while the remaining three vertices form the triangle. Thus \(\omega(G)=3\) as well.
Check: The coloring gives adjacent endpoint colors \(1,2\) on \(ab\), \(3,1\) on \(ac\), \(2,1\) on \(bc\), \(3,1\) on \(ad\), and \(2,1\) on \(be\). All five edges have different colors at their endpoints.
Worked Example: Restricting the Ordering to an Induced Subgraph
Use the same graph and PEO \(d,a,c,b,e\), and take \(S=\{a,b,d,e\}\). The induced subgraph has \(V(G[S])=\{a,b,d,e\}\) and \(E(G[S])=\{ab,ad,be\}\); the edge \(bc\) is absent because \(c\notin S\). The restricted ordering is \(d,a,b,e\). Its later-neighbor sets are \(\{a\}\) for \(d\), \(\{b\}\) for \(a\), \(\{e\}\) for \(b\), and the empty set for \(e\), so it is a PEO.
Color in reverse order \(e,b,a,d\). Give \(e\) color 1, \(b\) color 2, \(a\) color 1, and \(d\) color 2. The edges \(ab,ad,be\) have endpoint colors \(2,1\), \(1,2\), and \(2,1\), respectively, so this is a proper two-coloring. The edge \(ab\) is a clique of size two, and there is no triangle because the graph has only the three listed edges. Therefore \(\chi(G[S])=\omega(G[S])=2\).
Check: The graph is the path \(d-a-b-e\), which has four vertices and three edges. The coloring alternates along its three edges, so every adjacent pair receives different colors; the edge \(ab\) rules out a one-coloring.
Worked Example: A Chordal Graph with Two Components
Let \(G\) have \(V(G)=\{1,2,3,4,5,6\}\) and \(E(G)=\{12,23,31,45\}\). Its components are a triangle on \(\{1,2,3\}\), an edge on \(\{4,5\}\), and an isolated vertex \(6\). One PEO is \(1,2,3,4,5,6\): the later neighbors of \(1\) are \(\{2,3\}\), an adjacent pair; those of \(2\) are \(\{3\}\); those of \(3\) are empty; and those of \(4,5,6\) are, respectively, \(\{5\}\), the empty set, and the empty set.
The triangle requires three colors. Assign colors 1, 2, and 3 to vertices 1, 2, and 3; assign colors 1 and 2 to 4 and 5; and assign color 1 to 6. The edge \(45\) has different endpoint colors, and the triangle edges \(12,23,31\) also have different endpoint colors. Thus \(\chi(G)=3\). The largest clique is the triangle, so \(\omega(G)=3\).
For an induced subgraph containing vertices from several components, the same reasoning applies component by component: there are no edges between components, so colors can be reused across them. More formally, a clique lies within a single component, and a coloring of each component can use a common palette whose size is the largest chromatic number of any component. This illustrates why isolated vertices and disconnected graphs do not require a separate exception in the theorem.
Check: The edge set has four edges: three in the triangle and one joining 4 to 5. The displayed coloring uses three colors because of the triangle, and no clique can exceed its three vertices.
Why the Induced-Subgraph Condition Matters
The adjective “perfect” is stronger than saying that the whole graph has equal clique and chromatic numbers. The definition requires equality after every vertex subset is retained and all edges among the retained vertices are kept. That is why the proof first addresses arbitrary induced subgraphs, rather than stopping once it colors the original graph.
A useful contrast is the five-cycle. Let \(C_5\) have \(V=\{1,2,3,4,5\}\) and \(E=\{12,23,34,45,51\}\). Its largest clique has size two: it has edges, but no triangle, so \(\omega(C_5)=2\). It cannot be colored with two colors. Starting with color 1 on vertex 1 forces colors 2, 1, 2, and 1 successively on vertices 2, 3, 4, and 5; then edge \(51\) has both endpoints colored 1. But three colors suffice: assign colors \(1,2,1,2,3\) to vertices \(1,2,3,4,5\). Each listed edge has differently colored endpoints, so \(\chi(C_5)=3\). Thus \(C_5\) is not perfect. It is not chordal either, since its full five-cycle is induced. This example shows a failure of perfection outside the chordal class, not that every nonchordal graph fails to be perfect.
Common Pitfall
A frequent error is to count the already-colored neighbors of \(v_i\) and conclude that they use at most \(\omega(G)\) colors, which would not guarantee an available color from a palette of that size. The needed bound is sharper: those neighbors form a clique, and adjoining \(v_i\) gives a clique too. Therefore, if there are \(r\) such neighbors, \(r+1\leq\omega(G)\), so \(r\leq\omega(G)-1\). At least one color remains. Also track the coloring direction correctly: when an edge has one endpoint colored earlier in the reverse ordering, it is the endpoint colored later that is now assigned a color different from the already-colored endpoint.
Check Your Understanding
Use the ordering argument and the definition of perfection to answer these questions.
- Why does the PEO condition imply that the already-colored neighbors of a vertex form a clique when coloring in reverse order?
- If a vertex has \(r\) already-colored neighbors in the proof, explain why \(r\leq\omega(G)-1\), not merely \(r\leq\omega(G)\).
- Let \(G\) have vertices \(\{p,q,r,s\}\) and edges \(\{pq,qr,rs\}\). Give a PEO and use reverse order to produce a proper coloring with two colors.
- Why does equality \(\chi(G)=\omega(G)\) for a graph \(G\) alone not establish that \(G\) is perfect?
- Explain why an induced subgraph of a chordal graph is chordal, and how the chordal–PEO characterization then applies to it.