2026-07-22T18:58:13Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:20568 2024-11-27T23:17:44Z ddc:004 open_access

Generalizing Roberts' Characterization of Unit Interval Graphs Ardévol Martínez, Virginia Rizzi, Romeo Saffidine, Abdallah Sikora, Florian Vialette, Stéphane Interval graphs Multiple Interval Graphs Unit Interval Graphs Characterization For any natural number d, a graph G is a (disjoint) d-interval graph if it is the intersection graph of (disjoint) d-intervals, the union of d (disjoint) intervals on the real line. Two important subclasses of d-interval graphs are unit and balanced d-interval graphs (where every interval has unit length or all the intervals associated to a same vertex have the same length, respectively). A celebrated result by Roberts gives a simple characterization of unit interval graphs being exactly claw-free interval graphs. Here, we study the generalization of this characterization for d-interval graphs. In particular, we prove that for any d ⩾ 2, if G is a K_{1,2d+1}-free interval graph, then G is a unit d-interval graph. However, somehow surprisingly, under the same assumptions, G is not always a disjoint unit d-interval graph. This implies that the class of disjoint unit d-interval graphs is strictly included in the class of unit d-interval graphs. Finally, we study the relationships between the classes obtained under disjoint and non-disjoint d-intervals in the balanced case and show that the classes of disjoint balanced 2-intervals and balanced 2-intervals coincide, but this is no longer true for d > 2. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Virginia Ardévol Martínez and Romeo Rizzi and Abdallah Saffidine and Florian Sikora and Stéphane Vialette 2024 Is Part Of LIPIcs, Volume 306, 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2024.12 urn:nbn:de:0030-drops-205687 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2024.12 eng https://creativecommons.org/licenses/by/4.0/legalcode