A Note on Quasi‐triangulated Graphs
Ion Gorgos, Chı́nh T. Hoàng, Vitaly Voloshin · SIAM Journal on Discrete Mathematics · 2006
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.