Generalizing Roberts' characterization of unit interval graphs
<|reference_start|>Generalizing Roberts' characterization of unit interval graphs: 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 \geq 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 \emph{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$.<|reference_end|>
@article{martínez2024generalizing,
    title={Generalizing Roberts' characterization of unit interval graphs},
    author={Virginia Ard'evol Mart'inez, Romeo Rizzi, Abdallah Saffidine,
  Florian Sikora, St'ephane Vialette},
    journal={arXiv preprint arXiv:2404.17872},
    year={2024},
    archivePrefix={arXiv},
    eprint={2404.17872},
    primaryClass={cs.DM cs.DS}
}