Linear oriented chromatic number for bounded-degeneracy graphs

About 3 years old · traced to

For an integer d≥1d\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 d≥1d\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.

References

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.