Chordal Directed Graphs Are Not $\chi$-Bounded

Pierre Aboulker, Nicolás Bousquet, Rémi de Joannis de Verclos · The Electronic Journal of Combinatorics · 2022

We show that digraphs with no transitive tournament on $3$ vertices and in which every induced directed cycle has length $3$ can have arbitrarily large dichromatic number. This answers in the negative a question of Carbonero, Hompe, Moore, and Spirkl (and strengthens one of their results).

Read the paper · More papers on PaperTik