Abstract
The HHD-free graphs are a class of perfect graphs that strictly contain the cographs, the chordal graphs, the Matula-perfect graphs, and the Welsh-Powell opposition graphs. In this paper we present two characterizations of the HHD-free graphs and show how to use them to produce a parallel recognition algorithm which runs in O(log n) time using O(n 4) processors on a concurrent-read, concurrent-write parallel random access machine.