User:David Eppstein/Perfect Graphs
| ||||||||
Perfect Graphs
[edit]- Background and definitions
- Graph theory
- Undirected graphs
- Cliques
- Independent sets
- Graph coloring
- Clique cover
- Induced cycle
- Perfect graph
- Structure theorems and perfection-preserving graph operations
- Complement graph
- Induced subgraph
- Skew partition
- Lexicographic product of graphs
- Perfect graph theorem
- Strong perfect graph theorem
- Bipartite graphs, their line graphs, and their matchings
- Bipartite graph
- Line graph
- Matching (graph theory)
- Hall's marriage theorem
- Kőnig's theorem (graph theory)
- Dulmage–Mendelsohn decomposition
- Rook's graph
- Chains and antichains in partial orders
- Partially ordered set
- Comparability graph
- Dilworth's theorem
- Mirsky's theorem
- Cograph
- Threshold graph
- Trivially perfect graph
- Permutation graph
- Chordal and interval graphs
- Chordal graph
- Interval graph
- Apollonian network
- Block graph
- Indifference graph
- K-tree
- Leaf power
- Maximal outerplanar graph
- Ptolemaic graph
- Split graph
- Strongly chordal graph
- Windmill graph
- Other classes of perfect graphs
- Distance-hereditary graph
- Line perfect graph
- Meyniel graph
- Parity graph
- Perfectly orderable graph
- Tolerance graph
- Trapezoid graph