Chordal, interval, and circular-arc product graphs

A graph G is chordal if every cycle of length at least 4 in G has a chord, interval if it is the intersection graph of a family of closed intervals on the real line, and circular-arc if it is the intersection graph of a set of closed arcs on a circle. The classes of chordal, interval, and circular-arc graphs are well known and well studied in the literature. Every interval graph is both a chordal and a circular-arc graph; both inclusions are proper. Chordal graphs and interval graphs are subclasses of the class of perfect graphs. For more information on these graph classes we refer the reader to [7, 14, 5, 8, 2, 15], for example. In this paper we consider the four standard graph products: the Cartesian product, the strong product, the direct product, and the lexicographic product. For each of these four products, we completely characterize when a nontrivial product of two graphs G and H is chordal, interval, or circular-arc, respectively. While the characterizations for chordal and interval graphs are rather straightforward and can be proved directly, the characterizations of circular-arc product graphs are more involved and are derived using characterizations of 1-perfectly orientable product graphs (for each of the four standard products) due to Hartinger and