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

Stimulated by challenges for the dichromatic number, the authors establish that the family of graphs where each triangle-free induced subgraph has bounded chromatic number is not \(\chi\)-bounded. They also raise a number of open problems for the researchers who are interested in this topic. In fact, they ask in particular, whether the family of digraphs with every induced directed cycle of length \(t\), is \(\vec{\chi}\)-bounded for a fixed integer \(t>3\). \textit{P. Aboulker} et al. [ibid. 29, No. 2, Research Paper P2.17, 5 p. (2022; Zbl 1493.05130)] answered the authors' question in the negative for \(t = 3\). The authors in this article extend this negative answer to all \(t\) greater than or equal to 3. Even though \(t\)-chordal graphs are not \(\vec{\chi}\)-bounded the authors establish that deciding whether a digraph is \(t\)-chordal is coNP-complete.