ON POWERS OF M-TRAPEZOID GRAPHS

First a new class of graphs is introduced: m-trapezoid graphs are the intersection graphs of m-trapezoids, where an m-trapezoid is given by m + 1 intervals on m fl parallel lines. The main result of this paper is that if G(k-1) is an m-trapezoid graph then G(k) is also an m-trapezoid graph. This theorem has some interesting corollaries concerning interval graphs, trapezoid graphs and cocomparability graphs: If A is either of these classes, then G(k-1) is an element of A implies G(k) is an element of A. This answers an open question of P. Damaschke.