ON THE CHORDALITY OF A GRAPH

The chordality of a graph G = (V, E) is defined as the minimum k such that we can write E = E1 and ... and E(k) with each (V, E(i)) a chorda l graph. We present several results bounding the value of this general ization of boxicity. Our principal result is that the chordality of a graph is at most its tree width. In particular, series-parallel graphs have chordality at most 2. Potential strengthenings of this statement fail in that there are planar graphs with chordality 3 and series-par allel graphs with boxicity 3.