Proving a directed analogue of the Gyárfás-Sumner conjecture for orientations of \(P_4\) (Q6199196): Difference between revisions

Summary: An oriented graph is a digraph that does not contain a directed cycle of length two. An (oriented) graph \(D\) is \(H\)-free if \(D\) does not contain \(H\) as an induced sub(di)graph. The Gyárfás-Sumner conjecture is a widely-open conjecture on simple graphs, which states that for any forest \(F\), there is some function \(f\) such that every \(F\)-free graph \(G\) with clique number \(\omega(D)\) has chromatic number at most \(f(\omega(D))\). \textit{P. Aboulker} et al. [ibid. 28, No. 2, Research Paper P2.27, 19 p. (2021; Zbl 1470.05049)] proposed an analogue of this conjecture to the dichromatic number of oriented graphs. The dichromatic number of a digraph \(D\) is the minimum number of colors required to color the vertex set of \(D\) so that no directed cycle in \(D\) is monochromatic. Aboulker et al.'s [loc. cit.] \(\overrightarrow{\chi}\)-boundedness conjecture states that for every oriented forest \(F\), there is some function \(f\) such that every \(F\)-free oriented graph \(D\) has dichromatic number at most \(f(\omega(D))\), where \(\omega(D)\) is the size of a maximum clique in the graph underlying \(D\). In this paper, we perform the first step towards proving \(\overrightarrow{\chi}\)-boundedness conjecture [Aboulker et al., loc. cit.] by showing that it holds when \(F\) is any orientation of a path on four vertices.