The oriented Gyárfás–Sumner conjecture
The oriented Gyárfás–Sumner conjecture
Let be an oriented forest. For a digraph , let be the clique number of its underlying graph and let be its dichromatic number, the minimum number of acyclic induced subdigraphs into which its vertices can be partitioned. Let be the class of digraphs with no induced subdigraph isomorphic to . A class of digraphs is dichromatically bounded if there is a function such that every digraph in the class satisfies .
Oriented Gyárfás–Sumner conjecture. For any oriented forest , 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
Sign in to submit a solution.
No solutions have been posted yet.