Paperlane

no. 14 · Friday 13 November 2026

A characterization of interval nest digraphs

Ayelén Alcantar, Flavia Bonomo, Guillermo Durán and Nina Pardal

math.CO · v2

Abstract

A digraph consisting of a set of vertices $V$ and a set of arcs $E$ is called an interval digraph if there exists a family of closed intervals $\{I_u,J_u\}_{u \in V}$ such that $uv$ is an arc if and only if the intersection of $I_u$ and $J_v$ is non-empty. Interval digraphs naturally generalize interval graphs, by extending the classical interval intersection model to directed graphs. Several subclasses of interval digraphs have been studied in the literature-such as balanced, chronological and catch interval digraphs-each characterized by admitting interval representations that satisfy specific restrictions. Among these, interval nest digraphs are the ones that admit an interval representation in which $J_u$ is contained in $I_u$ for all vertices $u$ of $V$. In this work, we provide a complete characterization of interval nest digraphs in terms of vertex linear orderings with forbidden patterns, which we call nest orderings. This result completes the picture of vertex-ordering characterizations among the main subclasses of interval digraphs.

comments
Small mistake correction with respect to the published version. A necessary condition in a related paper was (wrongly) stated buy us as a characterization, we have now corrected that mistake
journal
Discrete Applied Mathematics 395 (2026), 337-344
fields
Combinatorics
pdf ↗ page arXiv:2603.08585 ↗