Chordal directed graphs are not \(\chi\)-bounded (Q2138574): Difference between revisions

Let \(D\) be a digraph without a directed cycle of length two. A partition of the vertices of \(D\) into \(k\) parts is called a \(k\)-dicoloring of \(D\) if none of the subdigraphs induced by parts has a directed cycle. The smallest integer \(k\) such that \(D\) has a \(k\)-dicoloring is called the dichromatic number of \(D\) and is denoted by \(\overset{\to}{\chi}(D)\). A class \(\mathcal{G}\) of digraphs is \(\overset{\to}{\chi}\)-bounded if there exists a function \(f\) such that \(\overset{\to}{\chi}(D) \leq f(\omega(D))\) for every \(D \in \mathcal{G}\), where \(\omega(D)\) denotes the clique number of the underlying graph of \(D\). Let \(\mathcal{C}_3\) be the class of digraphs with neither a transitive tournament on three vertices nor an induced directed cycle of the length of least four. The main result established in this paper is the following statement. For every \(k\), there exists \(D \in \mathcal{C}_3\) such that \(\overset{\to}{\chi}(D) \geq k\).