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 P2 (α-perfection), and satisfy P1 (χ-perfection). These two results, in large measure, inspired the conjecture that P1 and P2 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 ...

Get Algorithmic Graph Theory and Perfect Graphs, 2nd Edition now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.