Subquadratic growth conjecture for acyclic subgraphs of tournaments
Let denote the maximum chromatic number of an acyclic subgraph of an oriented graph . Let be the smallest integer such that every tournament with more than vertices has .
Subquadratic growth conjecture.
This conjecture asks for an asymptotic improvement over the general product-coloring bound . The paper proves the modest improvement , but the conjectured subquadratic bound remains open.
References
Primary source
Safwat Nassar and Raphael Yuster, “Acyclic subgraphs with high chromatic number”, arXiv:1811.05734 (2018).
Additional references
2 papers in this index state this conjecture (2014–2018). The statement above is taken from the most recent of them; the others are arXiv:1401.0489.
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
No solutions have been posted yet.