{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,23]],"date-time":"2026-08-23T15:54:51Z","timestamp":1787500491023,"version":"build-2736575974"},"reference-count":0,"publisher":"The Electronic Journal of Combinatorics","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Electron. J. Combin."],"abstract":"<jats:p>The dichromatic number of a digraph $D$ is the minimum number of colors needed to color its vertices\u00a0 in such a way that each color class induces an acyclic digraph. As it generalizes the notion of the chromatic number of graphs, it has become the focus of numerous works. In this work we look at possible extensions of the Gy\u00e1rf\u00e1s-Sumner conjecture. In particular, we conjecture a simple characterization\u00a0 of sets $\\mathcal F$ of three digraphs such that every digraph with sufficiently large dichromatic number must contain a member of $\\mathcal F$ as an induced subdigraph.\u00a0\r\nAmong notable results, we prove that oriented $K_4$-free graphs without a directed path of length $3$ have bounded dichromatic number where a bound of $414$ is provided. We also show that an orientation of a complete multipartite graph with no directed triangle is $2$-colorable. To prove these results we introduce the notion of nice sets that might be of independent interest.<\/jats:p>","DOI":"10.37236\/9906","type":"journal-article","created":{"date-parts":[[2021,5,20]],"date-time":"2021-05-20T23:11:25Z","timestamp":1621552285000},"source":"Crossref","is-referenced-by-count":8,"title":["Extension of Gy\u00e1rf\u00e1s-Sumner Conjecture to Digraphs"],"prefix":"10.37236","volume":"28","author":[{"given":"Pierre","family":"Aboulker","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Pierre","family":"Charbit","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Reza","family":"Naserasr","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"23455","published-online":{"date-parts":[[2021,5,21]]},"container-title":["The Electronic Journal of Combinatorics"],"original-title":[],"link":[{"URL":"https:\/\/www.combinatorics.org\/ojs\/index.php\/eljc\/article\/download\/v28i2p27\/pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.combinatorics.org\/ojs\/index.php\/eljc\/article\/download\/v28i2p27\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,20]],"date-time":"2021-05-20T23:11:26Z","timestamp":1621552286000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.combinatorics.org\/ojs\/index.php\/eljc\/article\/view\/v28i2p27"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,5,21]]},"references-count":0,"journal-issue":{"issue":"2","published-online":{"date-parts":[[2021,4,9]]}},"URL":"https:\/\/doi.org\/10.37236\/9906","relation":{},"ISSN":["1077-8926"],"issn-type":[{"value":"1077-8926","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,5,21]]},"article-number":"P2.27"}}