{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,2]],"date-time":"2026-09-02T02:15:50Z","timestamp":1788315350239,"version":"build-2803163510"},"reference-count":0,"publisher":"The Electronic Journal of Combinatorics","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Electron. J. Combin."],"abstract":"<jats:p>Interval graphs admit elegant structural characterizations and linear time recognition\u00a0algorithms; on the other hand, the usual interval digraphs lack a forbidden\u00a0structure characterization as well as a low-degree polynomial time recognition algorithm.\u00a0In this paper we identify another natural digraph analogue of interval graphs\u00a0that we call \u201dchronological interval digraphs\u201d. By contrast, the new class admits\u00a0both a forbidden structure characterization and a linear time recognition algorithm.\u00a0Chronological interval digraphs arise by interpreting the standard definition of an interval\u00a0graph with a natural orientation of its edges. Specifically, $G$ is a chronological\u00a0interval digraph if there exists a family of closed intervals $I_v$, $v \\in V(G)$, such that $uv$\u00a0is an arc of $G$ if and only if $I_u$\u00a0intersects $I_v$\u00a0and the left endpoint of $I_u$\u00a0is not greater\u00a0than the left endpoint of $I_v$. (Equivalently, if and only if $I_u$\u00a0contains the left endpoint\u00a0of $I_v$.)We characterize chronological interval digraphs in terms of vertex orderings, in\u00a0terms of forbidden substructures, and in terms of a novel structure of so-called $Q$-paths.\u00a0The first two characterizations exhibit strong similarity with the corresponding\u00a0characterizations of interval graphs. The last characterization leads to a linear\u00a0time recognition algorithm.<\/jats:p>","DOI":"10.37236\/2497","type":"journal-article","created":{"date-parts":[[2020,1,11]],"date-time":"2020-01-11T01:24:23Z","timestamp":1578705863000},"source":"Crossref","is-referenced-by-count":5,"title":["Recognition and Characterization of Chronological Interval Digraphs"],"prefix":"10.37236","volume":"20","author":[{"given":"Sandip","family":"Das","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Mathew","family":"Francis","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Pavol","family":"Hell","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jing","family":"Huang","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"23455","published-online":{"date-parts":[[2013,7,26]]},"container-title":["The Electronic Journal of Combinatorics"],"original-title":[],"link":[{"URL":"https:\/\/www.combinatorics.org\/ojs\/index.php\/eljc\/article\/download\/v20i3p5\/pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.combinatorics.org\/ojs\/index.php\/eljc\/article\/download\/v20i3p5\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,1,17]],"date-time":"2020-01-17T11:16:37Z","timestamp":1579259797000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.combinatorics.org\/ojs\/index.php\/eljc\/article\/view\/v20i3p5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,7,26]]},"references-count":0,"journal-issue":{"issue":"3","published-online":{"date-parts":[[2013,7,19]]}},"URL":"https:\/\/doi.org\/10.37236\/2497","relation":{},"ISSN":["1077-8926"],"issn-type":[{"value":"1077-8926","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,7,26]]},"article-number":"P5"}}