Exponential lower-bound conjecture for the oriented chromatic number of degenerate graphs
Exponential lower-bound conjecture for the oriented chromatic number of degenerate graphs
Let graphs be graphs in which every subgraph has a vertex of degree at most , and let denote the oriented chromatic number of a graph . For a positive integer , let be a graph on vertices. Exponential lower-bound conjecture. There exists a constant such that for all , there are infinitely many integers , and -degenerate graphs on vertices with
The conjecture asserts that the exponential dependence on the degeneracy parameter 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
Sign in to submit a solution.
No solutions have been posted yet.