Subquadratic growth conjecture for acyclic subgraphs of tournaments

About 12 years old · traced to

Let f(G)f(G) denote the maximum chromatic number of an acyclic subgraph of an oriented graph GG. Let g(n)g(n) be the smallest integer such that every tournament GG with more than g(n)g(n) vertices has f(G)>nf(G)>n.

Subquadratic growth conjecture.

g(n)=o(n2).g(n)=o(n^2).

This conjecture asks for an asymptotic improvement over the general product-coloring bound g(n)≤n2g(n)\leq n^2. The paper proves the modest improvement g(n)≤n2−(2−1/2)n+2g(n)\leq n^2-(2-1/\sqrt{2})n+2, 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

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.