Document Type

Article

Publication Date

2006

Department

Physics & Computer Science

Abstract

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.

Comments

This article was originally published in SIAM Journal on Discrete Mathematics, 20(3): 597-602. © 2006 Society for Industrial and Applied Mathematics

Download

Share

COinS