Tournament Gyárfás–Sumner conjecture for forest backedge graphs

Let TT be a tournament with an ordering of its vertices, and let the corresponding backedge graph be the graph whose edges are the arcs directed backwards in that ordering. A tournament class is dichromatically bounded by clique number if there is a function ff such that every tournament in the class satisfies

χ(T)f(ω(T)).\operatorname{\overrightarrow{\chi}}(T)\leq f(\operatorname{\overrightarrow{\omega}}(T)).

Tournament Gyárfás–Sumner conjecture. If TT has a backedge graph that is a forest, then the class of tournaments not containing TT as a subgraph is dichromatically bounded by clique number. The source states this as an analogue of the Gyárfás–Sumner conjecture and does not give a resolution here.

Sources & referencesView supporting material

Primary source

Guillaume Aubian, “Computing the clique number of tournaments”, arXiv:2401.07776 (2024).

Progress summary

Never refreshed

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

Solutions 0

No solutions have been posted yet.