On the semi-perfect elimination (Q1825204)

The authors give algorithmic characterizations of two classes of graphs, those for which every ordering produced by the lexicographic breath-first search and the maximum cardinality search, respectively, is a semi- perfect elimination. A vertex x in G is semi-simplicial if x is the midpoint of no \(P_ 4\) in G (a \(P_ 4\) is a chordless path of 4 vertices and 3 edges). A linear ordering of G is a semi-perfect elimination if when the vertices of G are indexed by the linear order, \(x_ 1,x_ 2,...,x_ n\), then \(x_ i\) is a semi-simplicial vertex in the subgraph generated by \(x_ i,x_{i+1},...,x_ n\). After characterizing these two classes of graphs, the authors present algorithms for quickly finding the largest clique, largest stable set and minimal coloring in such graphs.