On the on-line chromatic number of the family of on-line 3-chromatic graphs (Q1916112)

Let \(G\) be a graph and assume that its vertex set has been linearly ordered. An on-line colouring of \(G\) is a proper colouring which colours vertices of \(G\) consistently with the order in such a way that at the \(i\)th step only the first \(i\) vertices and the adjacencies between them are known. The on-line chomatic number \(\chi^*(G)\) of \(G\) is the smallest number of colours sufficient for any on-line colouring of \(G\). \textit{A. Gyárfás} and \textit{J. Lehel} [J. Graph Theory 12, No. 2, 217-227 (1988; Zbl 0657.05026)] considered the on-line chromatic number of the class OL(3) of all graphs that can be on-line coloured with three colours and showed that \(4\leq \chi^*(\text{OL} (3))\leq16\). This paper establishes \(\chi^* (\text{OL}(3))=4\).