Physics & Computer Science
A graph is quasi-triangulated if each of its induced subgraphs has a vertex which is either simplicial (its neighbors form a clique) or cosimplicial (its nonneighbors form an independent set). We prove that a graph G is quasi-triangulated if and only if each induced subgraph H of G contains a vertex that does not lie in a hole, or an antihole, where a hole is a chordless cycle with at least four vertices, and an antihole is the complement of a hole. We also present an algorithm that recognizes a quasi-triangulated graph in O(nm) time.
Gorgos, Ion; Hoàng, Chính T.; and Voloshin, Vitaly, "A Note on Quasi-Triangulated Graphs" (2006). Physics and Computer Science Faculty Publications. 72.
This article was originally published in SIAM Journal on Discrete Mathematics, 20(3): 597-602. © 2006 Society for Industrial and Applied Mathematics