Graphs whose powers are chordal and graphs whose powers are interval graphs

The main theorem of this paper gives a forbidden induced subgraph condition on G that is sufficient for chordality of G^m. This theorem is a generalization of a theorem of Balakrishnan and Paulraja who had provided this only for m = 2. We also give a forbidden subgraph condition on G that is sufficient for chordality of G^2m. Similar conditions on G that are sufficient for G^m being an interval graph are also obtained. In addition it is easy to see, that no family of forbidden (induced) subgraphs of G is necessary for G^m being chordal or interval graph. © 1997 John Wiley & Sons, Inc.