Harutyunyan–Mohar conjecture for oriented graphs

At least 11 years old · documented by

Let DD be an oriented graph, meaning a digraph with no biclique of order greater than 11. Let Δ~(D)=max⁡v∈V(D)d+(v)d−(v)\widetilde{\Delta}(D)=\max_{v\in V(D)}\sqrt{d^+(v)d^-(v)} be its maximum geometric mean of in- and out-degrees, and let χ⃗(D)\vec\chi(D) be its dichromatic number, the minimum number of colours whose colour classes induce acyclic subdigraphs.

Harutyunyan–Mohar conjecture. Every oriented graph DD satisfies

χ⃗(D)≤⌈Δ~(D)2⌉+1.\vec\chi(D)\leq\left\lceil\frac{\widetilde{\Delta}(D)}{2}\right\rceil+1.

This is the proposed oriented-graph analogue of Reed's conjecture. The paper records partial upper bounds but leaves this conjecture open.

References

Primary source

Ken-ichi Kawarabayashi and Lucas Picasarri-Arrieta, “An analogue of Reed's conjecture for digraphs”, arXiv:2407.05827 (2025).

Additional references

2 papers in this index state this conjecture (2014–2024). The statement above is taken from the most recent of them; the others are arXiv:1409.7535.

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.