A 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)5 t is NP-complete.
Finally, the problem of determining whether a given graph is t-interval is NP-complete for t ≥ 2 REF .
Recognizing graphs with fixed interval number is NP-complete
Discret. Appl. Math.
Discret. Appl. Math.
Mathematics Computer Science