A characterization of some graph classes with no long holes (Q1898735)

The authors' main result is in some way a generalization of the next two theorems. T1 (Dirac, 1961): \(G\) is a triangulated graph, iff each induced subgraph \(H\) of \(G\) is a clique or has two nonadjacent simplicial vertices of \(H\). T2 (Chvátal, Rusu, 1993): A graph contains no holes, iff each of its subgraphs \(H\) with at least one edge contains an edge that is not middle of any chordless path \(P_4\) on 4 vertices in \(H\). The authors study a hierarchy of graphs \(G\) without holes and without some antiholes (complements of holes). They receive the following theorem: A graph \(G\) on \(n\) vertices contains no holes and no antiholes with \(i\) vertices \((5\leq i\leq k+ 1\leq n)\), iff for every induced subgraph \(H\) of \(G\) with at least one edge, either \(H\) is inseparable and has at least \([\mu(H)/2]\) edges that are \(k\)-simplicial in \(H\), or \(H\) has two separable edges that are \(k\)-simplicial in \(H\). A graph \(H\) is inseparable if its any two edges with no common vertices belong to a path on 4 vertices in \(H\). The number \([\mu(H)/2]\) denotes the size of nontrivial connected component of a given inseparable induced subgraph \(H\) of \(G\). An edge in a graph \(G\) is \(k\)-simplicial if its vertices are not endpoints of a chordless path on \(k\) vertices in the complement of \(G\). The authors give also a corollary concerning chordal bipartite graphs.