On double and multiple interval graphs

In this paper we discuss a generalization of the familiar concept of an interval graph that arises naturally in scheduling and allocation problems. We define the interval number of a graph G to be the smallest positive integer t for which there exists a function f which assigns to each vertex u of G a subset f ( u ) of the real line so that f ( u ) is the union of t closed intervals of the real line, and distinct vertices u and v in G are adjacent if and only if f ( u ) and f ( v )meet. We show that (1) the interval number of a tree is at most two, and (2) the complete bipartite graph K m, n has interval number ⌈( mn + 1)/( m + n )⌉.