---
tag: RG03FNSPF2
kind: concept
name: Perfect
sources:
  - wikipedia: en:325802@r1373839425
    locator: Glossary of graph theory, section P
    note: adopted
    mention: wikipedia://en/325802#5NP6
    sections: [Summary]
inventory: [G13C3HF9GD]
---

## Summary

A perfect graph is a graph in which, in every induced subgraph, the chromatic number equals the clique number. The perfect graph theorem and strong perfect graph theorem are two theorems about perfect graphs, the former proving that their complements are also perfect and the latter proving that they are exactly the graphs with no odd holes or anti-holes.

A perfectly orderable graph is a graph whose vertices can be ordered in such a way that a greedy coloring algorithm with this ordering optimally colors every induced subgraph. The perfectly orderable graphs are a subclass of the perfect graphs.

A [[perfect matching|05ZPH8KF9K]] is a matching that saturates every vertex; see matching.

A perfect 1-factorization is a partition of the edges of a graph into perfect matchings so that each two matchings form a Hamiltonian cycle.