English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

For $t \ge 2$, let us call a digraph $D$ \emph{t-chordal} if all induceddirected cycles in $D$ have length equal to $t$. In a previous paper, we askedfor which $t$ it is true that $t$-chordal graphs with bounded clique numberhave bounded dichromatic number. Recently, Aboulker, Bousquet, and de Verclosanswered 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 largedichromatic number. In this paper, we extend their result, giving for each $t\ge 3$ a construction of digraphs with clique number at most $3$ andarbitrarily large dichromatic number, thus answering our question in thenegative. On the other hand, we show that a more restricted class, digraphswith no induced directed cycle of length less than $t$, and no induced directed$t$-vertex path, have bounded dichromatic number if their clique number isbounded. We also show the following complexity result: for fixed $t \ge 2$, theproblem of determining whether a digraph is $t$-chordal is coNP-complete.

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