We give a characterization of a hierarchy of graph classes with no long holes in which each class excludes some long antiholes. Al one end of the hierarchy is the class of graphs with no long holes. At the other end is the class of weakly triangulated graphs. The characterization has the flavor of that for triangulated graphs: G is a triangulated graph if and only if every induced subgraph H of G is either a clique or has two nonadjacent simplicial vertices of H. (C) 1995 Academic Press, Inc. [References: 7]
展开▼
