Harutyunyan–McDiarmid conjecture on acyclic sets in H-free oriented graphs

Let HH be an oriented graph, and let an HH-free oriented graph be one that does not contain HH as a not necessarily induced subdigraph. For an oriented graph DD, write α(D)\vec\alpha(D) for its maximum acyclic set size and χ(D)\vec\chi(D) for its dichromatic number. Harutyunyan–McDiarmid conjecture. For every oriented graph HH, there is ϵ>0\epsilon>0 such that every HH-free oriented graph DD of order nn satisfies

α(D)nϵandχ(D)n1ϵ.\vec\alpha(D)\geq n^\epsilon\qquad\text{and}\qquad \vec\chi(D)\leq n^{1-\epsilon}.

This conjecture is open even when HH is the directed cycle of length 33, and it strengthens the Alon–Pachs–Solymosi conjecture below.

Sources & referencesView supporting material

Primary source

Pierre Aboulker, Frédéric Havet, François Pirot and Juliette Schabanel, “Minimum acyclic number and maximum dichromatic number of oriented triangle-free graphs of a given order”, arXiv:2403.02298 (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.