On the on-line chromatic number of the family of on-line 3-chromatic graphs

Let the family OL(3) contain all graphs which can be colored on-line with 3 colors. Gyárfás and Lehel suggested the problem of determining the on-line chromatic number χ^*(OL(3)) of OL(3). They showed that 4 χ^*(OL(3)) 16. We present an algorithm that colors every on-line-3-chromatic graph with 4 colors. Thus χ^*(OL(3)) = 4.