The oriented Gyárfás–Sumner conjecture

From papers

Let \vvF\vv F be an oriented forest. For a digraph DD, let ω(D)\omega(D) be the clique number of its underlying graph and let χ(D)\overrightarrow{\chi}(D) be its dichromatic number, the minimum number of acyclic induced subdigraphs into which its vertices can be partitioned. Let Forbind(\vvF)\operatorname{Forb}_{\mathrm{ind}}(\vv F) be the class of digraphs with no induced subdigraph isomorphic to \vvF\vv F. A class of digraphs is dichromatically bounded if there is a function ff such that every digraph DD in the class satisfies χ(D)f(ω(D))\overrightarrow{\chi}(D)\leq f(\omega(D)).

Oriented Gyárfás–Sumner conjecture. For any oriented forest \vvF\vv F, Forbind(\vvF)\operatorname{Forb}_{\mathrm{ind}}(\vv F) is dichromatically bounded.

This is the directed analogue of the Gyárfás–Sumner conjecture. The paper studies this question through heroes in induced-subdigraph-free classes; the general conjecture remains open.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Pierre Aboulker, Guillaume Aubian, Pierre Charbit and Stéphan Thomassé, “(P6, triangle)-free digraphs have bounded dichromatic number”, arXiv:2212.02272 (2023).

Solutions 0

No solutions have been posted yet.