Harutyunyan–McDiarmid conjecture on acyclic sets in H-free oriented graphs
Harutyunyan–McDiarmid conjecture on acyclic sets in H-free oriented graphs
Let be an oriented graph, and let an -free oriented graph be one that does not contain as a not necessarily induced subdigraph. For an oriented graph , write for its maximum acyclic set size and for its dichromatic number. Harutyunyan–McDiarmid conjecture. For every oriented graph , there is such that every -free oriented graph of order satisfies
This conjecture is open even when is the directed cycle of length , 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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.