Exponential lower-bound conjecture for the oriented chromatic number of degenerate graphs

From papers

Let d-degenerated\text{-degenerate} graphs be graphs in which every subgraph has a vertex of degree at most dd, and let χo(G)\chi_o(G) denote the oriented chromatic number of a graph GG. For a positive integer nn, let GG be a graph on nn vertices. Exponential lower-bound conjecture. There exists a constant c>0c>0 such that for all d2d\geq 2, there are infinitely many integers nn, and dd-degenerate graphs GG on nn vertices with

χo(G)c2dn.\chi_o(G) \geq c 2^{d}\sqrt{n}.

The conjecture asserts that the exponential dependence on the degeneracy parameter dd is necessary for lower bounds on the oriented chromatic number. The preceding discussion motivates this through comprehensive graphs, but the proposed lower bound and the requested novel construction remain open in the source.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Alexander Clow, “MAD Phase Transitions in the Oriented Chromatic Number”, arXiv:2607.22915 (2026).

Additional references

26 papers in this index state this conjecture (2002–2026). The statement above is taken from the most recent of them; the others are arXiv:2510.20461, arXiv:2505.18804, arXiv:2412.19998, arXiv:2410.22611, arXiv:2207.09053, arXiv:2204.13406, arXiv:2004.00516, arXiv:1906.06036, arXiv:1807.11543, arXiv:1710.04146, arXiv:1708.07209, arXiv:1706.06330, and 13 more.

Solutions 0

No solutions have been posted yet.