Online Ohba conjecture

Let GG be a graph, with vertex number V(G)|V(G)|, chromatic number c7(G)c7(G), and on-line choice number chOL(G){\rm ch}^{\rm OL}(G). A graph is on-line chromatic-choosable when χ(G)=chOL(G)\chi(G)={\rm ch}^{\rm OL}(G). Online Ohba conjecture. If

V(G)2χ(G),|V(G)|\leqslant 2\chi(G),

then

χ(G)=chOL(G).\chi(G)={\rm ch}^{\rm OL}(G).

This is an on-line analogue of Ohba's conjecture, which was known to hold with the bound V(G)2χ(G)+1|V(G)|\leqslant 2\chi(G)+1 but fails in the on-line setting at that bound. The conjecture was proposed by Harutyunyan, Wigderson and Zhu and remains unresolved here.

Sources & referencesView supporting material

Primary source

Jakub Kozik, Piotr Micek and Xuding Zhu, “Towards on-line Ohba's conjecture”, arXiv:1111.5458 (2012).

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.