Alon–Pachs–Solymosi conjecture on acyclic sets in H-free tournaments
Alon–Pachs–Solymosi conjecture on acyclic sets in H-free tournaments
Let be a tournament. An -free tournament is one that does not contain as a not necessarily induced subdigraph. For a tournament , write for its maximum acyclic set size. Alon–Pachs–Solymosi conjecture. For every tournament , there exists such that every -free tournament of order satisfies
This conjecture is equivalent to the Erdős–Hajnal conjecture. It is known for a few types of tournaments , but remains wide open in general.
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.