McDiarmid–Mohar conjecture on acyclic chromatic number of oriented graphs
McDiarmid–Mohar conjecture on acyclic chromatic number of oriented graphs
Let be an oriented graph, meaning that at most one directed edge joins any pair of vertices. Write for its average maximum degree and let denote its acyclic chromatic number.
McDiarmid–Mohar conjecture. Every oriented graph satisfies
This conjecture predicts a logarithmic improvement over the greedy bound , 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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.