Finding houses and holes in graphs

A house is the complement of an induced path on five vertices. A hole is an induced cycle on five or more vertices. A domino is the cycle on six verti ces with a long chord. A graph is HH-free if it does not contain a house or a hole. A graph is HHD-free if it does not contain a house, or a hole, or a domino. We present O(n(3)) algorithms to recognize HH-free graphs and HHD -free graphs. The previous best algorithms for the problems run in O(n(4)) time. (C) 2001 Elsevier Science B.V. All rights reserved.