Conjecture on the maximum dichromatic number of oriented triangle-free graphs

At least 1 year old · documented by

For each positive integer nn, let t⃗(n)\vec t(n) be the maximum dichromatic number of an oriented triangle-free graph of order nn. Maximum dichromatic number conjecture.

t⃗(n)=Θ ⁣(nlog⁡n).\vec t(n)=\Theta\!\left(\sqrt{\frac{n}{\log n}}\right).

This conjecture is implied by the conjectured asymptotic order of the minimum acyclic number a⃗(n)\vec a(n) and would determine the maximum dichromatic number up to constant factors.

References

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.