Chordal Directed Graphs Are Not $\chi$-Bounded

  • Pierre Aboulker
  • Nicolas Bousquet
  • Rémi de Verclos
DOI: https://doi.org/10.37236/11050

Abstract

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).

Published
2022-05-06
How to Cite
Aboulker, P., Bousquet, N., & de Verclos, R. (2022). Chordal Directed Graphs Are Not $\chi$-Bounded. The Electronic Journal of Combinatorics, 29(2), P2.17. https://doi.org/10.37236/11050
Issue
Volume 29, Issue 2 (2022)
Article Number
P2.17