A CHARACTERIZATION OF GRAPHS WITH INTERVAL 2-STEP GRAPHS

One of the intriguing open problems on competition graphs is determini ng what digraphs have interval competition graphs. This problem origin ated in the work of Cohen on food webs. We consider it for the class o f loopless symmetric digraphs. The competition graph of a symmetric di graph D is the two-step graph of the underlying graph H of D, denoted S-2(H). The two-step graph is also known as the neighborhood graph, an d has been studied recently by Brigham and Dutton and by Boland, Brigh am and Dutton. This work was motivated by a paper of Raychaudhuri and Roberts where they investigated symmetric digraphs with a loop at each vertex. Under these assumptions, the competition graph is the square of the underlying graph H without loops. Here we first consider forbid den subgraph characterizations of graphs with interval two-step graphs . Second, we characterize a large class of graphs with interval two-st ep graphs using the Gilmore-Hoffman characterization of interval graph s.