Algorithmic Graph Theory and Perfect Graphs, 2nd Edition

Chapter 4

Triangulated graphs

Martin Charles Golumbic    Caesarea Rothschild Institute University of Haifa Haifa, Israel

Publisher Summary

One of the first classes of graphs to be recognized as being perfect was the class of triangulated graphs. Triangulated graphs satisfy the perfect property P₂ (α-perfection), and satisfy P₁ (χ-perfection). These two results, in large measure, inspired the conjecture that P₁ and P₂ were equivalent. The study of triangulated graphs can well be thought of as the beginning of the theory of perfect graphs. An undirected graph G is called triangulated if every cycle of length strictly greater than 3 possesses a chord—that is, an edge joining two nonconsecutive vertices of the cycle. Equivalently, G does not contain ...