McDiarmid–Mohar conjecture on acyclic chromatic number of oriented graphs

About 15 years old · traced to

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.

References

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.