Recognizing graphs with fixed interval number is NP-complete

AbstractA t-interval representation of a graph expresses it as the intersection graph of a family of subsets of the real line. Each vertex is assigned a set consisting of at most t disjoint closed intervals, in such a way that vertices are adjacent if and only if some interval for one intersects some interval for the other. The interval number i(G) of a graph G is the smallest number t such that G has a t-representation. We prove that, for any fixed value of t with t≥2, determining whether i(G)≤t is NP-complete