Digraphs with all induced directed cycles of the same length are not \(\vec{\chi}\)-bounded

Alvaro Carbonero¹ ; Patrick Hompe¹ ; Benjamin Moore² ; Sophie Spirkl¹

¹University of Waterloo
²Charles University, Institute of Computer Science, Prague, Czech Republic

The electronic journal of combinatorics, Tome 29 (2022) no. 4

Résumé

For $t \ge 2$, let us call a digraph $D$ t-chordal if all induced directed cycles in $D$ have length equal to $t$. In an earlier paper, we asked for which $t$ it is true that $t$-chordal graphs with bounded clique number have bounded dichromatic number. Recently, Aboulker, Bousquet, and de Verclos answered this in the negative for $t=3$, that is, they gave a construction of $3$-chordal digraphs with clique number at most $3$ and arbitrarily large dichromatic number. In this paper, we extend their result, giving for each $t \ge 3$ a construction of $t$-chordal digraphs with clique number at most $3$ and arbitrarily large dichromatic number, thus answering our question in the negative. On the other hand, we show that a more restricted class, digraphs with no induced directed cycle of length less than $t$, and no induced directed $t$-vertex path, have bounded dichromatic number if their clique number is bounded. We also show the following complexity result: for fixed $t \ge 2$, the problem of determining whether a digraph is $t$-chordal is coNP-complete.

Détail

DOI : 10.37236/11179

Classification : 05C15, 05C20, 68Q17
Mots-clés : digraphs, \(t\)-chordal, dichromatic number, clique number