Duchet-type theorems for powers of HHD-free graphs

AbstractUsing an idea due to P. Duchet in proving his well-known theorem on powers of chordal graphs, we shall describe some theorems of Duchet-type for powers of graphs that have no long induced cycles. In particular, our Duchet-type theorem for HHD-free graphs improves a recent result due to Dragan, Nicolai and Brandstädt; stating that odd powers of HHD-free graphs are also HHD-free