Proving a directed analogue of the Gyárfás-Sumner conjecture for orientations of P_4
share
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 ω(G) has chromatic number at most f(ω(G)). Aboulker, Charbit, and Naserasr [Extension of Gyárfás-Sumner Conjecture to Digraphs; E-JC 2021] 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, Charbit, and Naserasr's χ-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(ω(D)), where ω(D) is the size of a maximum clique in the graph underlying D. In this paper, we perform the first step towards proving Aboulker, Charbit, and Naserasr's χ-boundedness conjecture by showing that it holds when F is any orientation of a path on four vertices.
READ FULL TEXT