Bounding the chromatic number of dense digraphs by arc neighborhoods (Q6607842)

The chromatic number of a digraph (containing no digons) is the smallest number of induced acyclic subgraphs which cover its vertex set. Thus the chromatic number of a tournament is the smallest number of transitive tournaments which cover its vertex set. Famously an undirected graph \(G\) can be triangle-free but have large chromatic number \(\chi(G)\): however in \textit{A. Harutyunyan} et al. [J. Comb. Theory, Ser. B 138, 166--171 (2019; Zbl 1415.05064)] it is shown that this cannot happen for tournaments, resolving a question of Berger. More precisely, letting for a vertex \(v\) of a tournament \(N*{+}(v)\) denote the set of out neighbours of \(v\), we have that if the chromatic number of the tournament induced by \(N^{+}(v)\) is bounded above by \(t\) as \(v\) varies then the chromatic number of the whole tournament is at most \(f(t)\) for some function \(f\).\par A potential stronger version of this result focuses not just on the out neighbourhood but the neighbourhood of an arc. If \(e=uv\) is an arc of any digraph, its neighbourhood \(N(e)=N^{+}(v)\cap N^{-}(u)\) where \(N^{-}(u)\) is the in-neighbourhood of \(u\), i.e. all vertices which are in a directed triangle containing the arc \(uv\). The putative generalisation would be that if the chromatic number of the tournament induced by \(N(e)\) is bounded as \(e\) varies then the chromatic number of the tournament is bounded. This theorem was proved in \textit{T. Nguyen} et al. [``Some results and problems on tournament structure'', Preprint, arXiv:2306.02364 [math. CO] (2023)]. The authors give a different proof of the result. The proof depends on a result from the paper of Harutyunyan et al. mentioned above and also on ideas from a paper by the authors \textit{F. Klingelhoefer} and \textit{A. Newman} [Coloring tournaments with few colors: Algorithms and complexity, in ESA2023] They then extend their proof to digraphs with bounded independence number \(\alpha\) (largest size of a set of vertices containing no arcs): if a digraph \(D\) has independence number \(\alpha\) and the chromatic number of the digraph induced by \(N(e)\) is bounded, then the chromatic number of the tournament is bounded.\par As an application, the authors show the equivalence of two conjectures. The first, relating to undirected graphs, was made in \textit{M. El-Zahar} and \textit{P. Erdős} [Combinatorica 5, 295--300 (1985; Zbl 0596.05027)] and states that for all integers \(t,c,\geq 1\) there is \(d\geq 1\) such that if a graph \(G\) has \(\chi(G)\geq d\) but no complete subgraph of order at least \(t\), then there are subsets \(A, B\subseteq V(G)\) with the chromatic numbers of the subgraphs induced by \(A\) and \(B\) both being \(\geq c\) and with no edges from \(A\) to \(B\). The second is from \textit{Tung Nguyen} et al., [J. Comb. Theory, Ser. B 165, 211--222 (2024; Zbl 1530.05057)] and states that for all \(c\geq 0\) there is \(d\geq 0\) such that if \(T\) is a tournament with chromatic number at least \(d\) then there are two sets \(A. B, \subseteq V(T) \) such that all arcs between \(A\) and \(B\) go from \(A\) to \(B\). In the arxiv preprint by Nguyen, Scott and Seymour mentioned earlier, it is noted that the second conjecture implies the first, but they left open the question of whether the reverse implication holds: the authors show that it does.