Are bipartite graphs perfect?

Yes. Their induced subgraphs remain bipartite, and the relevant clique and coloring bounds coincide.

Is every subgraph of a perfect graph perfect?

Every induced subgraph is. Arbitrary edge deletion does not preserve perfection in general.

Does perfect mean planar?

No. Planarity and perfection describe different properties.

AI Glossary / Graphs and symbolic AI / Intermediate

Perfect Graph

Definition

A perfect graph is a finite simple undirected graph in which every induced subgraph can be colored using exactly as many colors as the size of its largest clique. This structural property links two otherwise different graph-optimization quantities.

What it means

A proper coloring assigns colors to vertices so that adjacent vertices receive different colors. The chromatic number is the minimum number needed. A clique is a set of vertices all connected to one another, so every vertex in that clique needs a different color.

Consequently, the largest clique always gives a lower bound on the number of colors. In a perfect graph that bound is sufficient, and it remains sufficient after selecting any subset of vertices and retaining every edge between them.

Perfect is a technical label. It does not mean that the network is complete, error-free, especially well connected or ideally designed for its business purpose.

How it works

To understand the definition, first form an induced subgraph by choosing vertices and keeping all original edges among them. Compare its minimum coloring size with its maximum clique size. The equality must hold for every such selection, including the entire graph.

Checking only the whole graph is insufficient. A graph can have equal clique and chromatic numbers while containing a smaller induced subgraph where they differ.

The strong perfect graph theorem supplies an equivalent characterization: neither the graph nor its complement contains a chordless odd cycle of length at least five. The complement connects exactly those distinct vertex pairs that the original graph leaves unconnected.

This characterization underlies recognition methods, but an implementation's performance still depends on its algorithm. A direct enumeration of relevant cycles can be expensive even though polynomial-time recognition algorithms exist. Recognition and finding an optimal coloring are also different computational tasks.

Three practical examples

1. Fixed-interval resource allocation: Represent each booking by a vertex and overlapping bookings by edges. The resulting interval graph is perfect, connecting the minimum number of identical resources with the largest mutually overlapping group under this model.

2. Conflict analysis: An analyst investigates whether a conflict graph belongs to a perfect class before selecting a coloring method. The graph's origin must justify the property; a familiar-looking drawing does not.

3. Algorithm education: A student compares even and odd cycles to see why the largest clique is not always enough to predict how many colors a graph needs.

Think of it this way

Think of a group of mutually conflicting meetings as an unavoidable demand for separate rooms. In a perfect conflict graph, the largest such group gives the room requirement, and this remains true for every subset of meetings.

The analogy assumes that edges capture all relevant conflicts and rooms are interchangeable. Capacity limits, equipment requirements or travel times can add constraints outside ordinary graph coloring.

Worked example

Take the four-cycle with edges A - B, B - C, C - D and D - A. There are no diagonal edges. Its largest clique has two vertices because no three vertices are pairwise adjacent. Two colors suffice: give A and C one color, and B and D another.

Its induced subgraphs are paths, isolated vertices or smaller combinations of these, and each also has matching clique and chromatic numbers. The four-cycle is therefore perfect.

Now consider a chordless five-cycle. Its largest clique still has size two, but two colors cannot close an odd cycle without assigning the same color to adjacent vertices. Three colors are necessary, so it is not perfect.

For a subtler example, take the disjoint union of that five-cycle and a triangle. The whole graph has clique number three and chromatic number three. Nevertheless, it is not perfect because the five-cycle remains an induced subgraph violating the required equality.

Illustrative case study

In a fictional project, Birch Scheduling builds a conflict graph for shared equipment. An analyst notices that a maximum clique and one optimal coloring both have size four, and initially calls the graph perfect.

A review points out that this checks only one graph, not all its induced subgraphs. The team examines the origin of the conflicts and uses an appropriate recognition procedure before relying on perfect-graph structure.

The lesson is about the scope of a mathematical property. Agreement between two numbers in one instance does not prove the stronger hereditary condition that the term requires.

Common misconceptions and mistakes

A perfect graph is necessarily complete. Many sparse graphs, including trees, are perfect.
Equality on the whole graph proves perfection. Every induced subgraph must satisfy it.
Induced subgraphs allow arbitrary edge deletion. They retain all original edges among selected vertices.
A perfect matching makes a graph perfect. These are unrelated uses of the word perfect.
Any coloring routine is optimal on a perfect graph. A general greedy routine can still use more colors than necessary with an unsuitable vertex order.

Business use

Perfect-graph structure can make a graph-based model more useful for resource allocation and optimization. It provides a reason that a natural clique lower bound can be attained, rather than merely hoping a heuristic solution is close.

Start by checking the modeling assumptions. An interval graph built from fixed bookings has different structure from a graph assembled from many kinds of business conflict. Adding constraints can change the graph class or require a richer optimization model.

Separate mathematical guarantees from software guarantees. Confirm what a library routine recognizes, whether it returns a coloring or only a Boolean result, and how it scales. A theoretical tractability result does not make every direct implementation suitable for a large production graph.

Check your understanding

Why is the disjoint union of a triangle and a five-cycle not perfect despite having clique and chromatic numbers both equal to three?

Answer: Its induced five-cycle has clique number two and chromatic number three, violating the definition.

Related terms

Graph coloring
chromatic number
clique
induced subgraph
complement graph
interval graph
bipartite graph
strong perfect graph theorem

Learn next

Draw a complete graph on five vertices, then delete edges to leave a five-cycle. Compare this arbitrary subgraph with induced subgraphs of the original complete graph to see why the word induced is essential.

Sources

NetworkX documents the definition, input scope and implementation limits: https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.perfect_graph.is_perfect_graph.html

Chudnovsky, Robertson, Seymour and Thomas prove the strong perfect graph theorem: https://arxiv.org/abs/math/0212070

The cycle calculations and Birch Scheduling case are original explanatory examples.

Previous: Perceptual robotics Next: Perfect hash function