Linear oriented chromatic number for bounded-degeneracy graphs

For an integer d1d\geq 1, let χo(G)\chi_o(G) denote the oriented chromatic number and χ2(G)\chi_2(G) the 22-dipath chromatic number of a graph GG.

Bounded-degeneracy linearity conjecture. For every integer d1d\geq 1, there exists a constant cc depending on dd such that

χo(G)cχ2(G)\chi_o(G)\leq c\chi_2(G)

for every graph GG with degeneracy at most dd.

The conjecture asks whether the upper bound for the oriented chromatic number in terms of the 22-dipath chromatic number can be made linear on every fixed-degeneracy graph class. Its status is not specified in the supplied text.

Sources & referencesView supporting material

Primary source

Peter Bradshaw, Alexander Clow and Jingwei Xu, “Injective edge colorings of degenerate graphs and the oriented chromatic number”, arXiv:2308.15654 (2023).

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.