Multiple interval graphs are a well-known generalization of interval graphs introduced in the 1970s to deal with situations arising naturally in scheduling and allocation. A (disjoint) d-intervals is the union of d (disjoint) intervals on the real line, and a graph G is a (disjoint) d-interval graph if it is the intersection graph of (disjoint) d-intervals. The numerous concrete applications of this class of graphs have led to the study of natural restrictions, such as unit multiple interval graphs (where every interval has unit length).
Whereas it has been known for a long time that recognizing 2-interval graphs and other related classes is NP-complete, the complexity of recognizing unit 2-interval graphs remained open for a long time. Here, we show that recognizing disjoint unit d-interval graphs is also NP-complete. On the positive side, we give a characterization of unit d-interval graphs which are also interval graphs, and a partial characterization of disjoint unit d-interval graphs which are also interval. This last result implies that the class of disjoint unit d-interval graphs is strictly included in the class of unit d-interval graphs.
Localisation
Salle de séminaire 4B125 (bâtiment Copernic)
5 Boulevard Descartes 77420 Champs-sur-Marne