McDiarmid–Mohar conjecture on acyclic chromatic number of oriented graphs

Let DD be an oriented graph, meaning that at most one directed edge joins any pair of vertices. Write Δˉ(D)\bar{\Delta}(D) for its average maximum degree and let χA(D)\chi_A(D) denote its acyclic chromatic number.

McDiarmid–Mohar conjecture. Every oriented graph DD satisfies

χA(D)=O(Δˉ(D)logΔˉ(D)).\chi_A(D) = O\left(\frac{\bar{\Delta}(D)}{\log \bar{\Delta}(D)}\right).

This conjecture predicts a logarithmic improvement over the greedy bound χA(D)Δˉ(D)+1\chi_A(D)\leq \bar{\Delta}(D)+1, in analogy with strong upper bounds for chromatic number in undirected graphs. The source presents it as an open conjecture attributed to McDiarmid and Mohar.

Sources & referencesView supporting material

Primary source

Noah Golowich, “The m-Degenerate Chromatic Number of a Digraph”, arXiv:1409.7535 (2018).

Additional references

3 papers in this index state this conjecture (2011–2014). The statement above is taken from the most recent of them; the others are arXiv:1110.4896, arXiv:1110.4898.

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.