Completeness for intersection classes

An intersection representation of a graph is a function gf mapping vertices to sets such that for any u ≠ v, u is adjacent to v iff gf(u) ∩ gf(v) ≠ . The intersection class defined by a set of sets ∑ is the set of all graphs having an intersection representation using sets from ∑. Interval graphs and chordal graphs are well-studied examples of intersection classes.

This paper introduces the notion of completeness for intersection classes. That is, determining precisely what restrictions can be made on the allowable sets without losing the power to represent any graph in the intersection class. The solution to this problem is presented for the chordal graphs.