A characterization of graphs with interval two-step graphs (Q1805321)

The two-step graph \(S_ 2(G)\) of a graph \(G= (V, E)\) is the graph \((V, E')\), where \(\{x, y\}\in E'\) iff \(x\) and \(y\) have a common neighbour. This concept is the undirected analog of competition graphs introduced in [\textit{J. Cohen}, Food webs and niche spaces, Princeton U.P., Princeton, N.J. (1968)]. It is first shown that if the girth of \(G\) is 5 or \(\geq 7\) then \(S_ 2(G)\) cannot be an interval graph. Then the Gilmore-Hoffman characterization of interval graphs is introduced: a graph \(G\) is interval iff the family of maximal cliques has a consecutive ranking---that is, can be ordered \(C_ 1,C_ 2,\dots, C_ r\) so that if \(v\in C_ i\) and \(v\in C_ k\), \(i\leq k\), then \(v\in C_ j\) for all \(j\) with \(i\leq j\leq k\). This characterization is used to find criteria for \(S_ 2(G)\) to be an interval graph for several classes of graphs: trees, graphs with neither triangles nor 6-cycles, graphs with no 6-cycles such that every edge is in a triangle, graphs with no 6- cycles, and graphs with no triangles such that no two 6-cycles share more than one edge.