We gratefully acknowledge support from
the Simons Foundation and member institutions.
Full-text links:

Download:

Current browse context:

cs.DM

Change to browse by:

References & Citations

DBLP - CS Bibliography

Bookmark

(what is this?)
CiteULike logo BibSonomy logo Mendeley logo del.icio.us logo Digg logo Reddit logo

Computer Science > Discrete Mathematics

Title: Generalizing Roberts' characterization of unit interval graphs

Abstract: 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$.
Subjects: Discrete Mathematics (cs.DM); Data Structures and Algorithms (cs.DS)
Cite as: arXiv:2404.17872 [cs.DM]
  (or arXiv:2404.17872v1 [cs.DM] for this version)

Submission history

From: Virginia Ardévol Martínez [view email]
[v1] Sat, 27 Apr 2024 11:49:04 GMT (261kb,D)

Link back to: arXiv, form interface, contact.