Suppose each vertex of a graph G is assigned a subset of the real line consisting of at most t closed intervals. This assignment is called a t-interval representation of G when vertex u is adjacent to vertex w if and only if some interval for u intersects some interval for w. The interval number i(G) of a graph G is the smallest number t such that G has a t-interval representation. It is proved that i(G) < 3 whenever G is planar and that this bound is the best possible. The related concepts of displayed interval number and depth-r interval number are discussed and their maximum values for certain classes of planar graphs are found.
The class of planar graphs is a subclass of 3-interval graphs REF .
The interval number of a planar graph: Three intervals suffice
J. Comb. Theory, Ser. B
J. Comb. Theory, Ser. B
Mathematics Computer Science