Perfect
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 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.
Further reading
- Wikipedia, page 325802, revision 1373839425, Glossary of graph theory, section P. adopted
About this page
| Tag | RG03FNSPF2 |
|---|---|
| URI | m2://RG03FNSPF2 |
| Kind | concept |
| Writing | W1 stated |
| Changed | 4 November 2026 |
Markdown · JSON · Edit on GitHub
What this page needs for W2
- edge defines in: at least one definition (0 of 1)
- edge instance_of in: at least two examples (0 of 2)
- edge not_instance_of in: at least one non-example (0 of 1)
- edge specializes both: the more general notions and the special cases (0 of 1)
The writing levels say how complete the text of a page is. They do not measure its truth.
What links here
No page links to this page yet.