Proving a Directed Analog of the Gyarfas-Sumner Conjecture for Orientations of <i>P</i>₄

Abstract

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 Gyarfas-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(G) has chromatic number at most f(omega(G)). Aboulker, Charbit, and Naserasr [Extension of Gyarfas-Sumner Conjecture to Digraphs, Electron. J. Comb., 2021] proposed an analog 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&apos;s ->-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 Aboulker, Charbit, and Naserasr&apos;s ->-chi-boundedness conjecture by showing that it holds when F is any orientation of a path on four vertices.Mathematics Subject Classifications: 05C88, 05C89