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. Gyarfas and Lehel suggested the problem of determining the on-line chromatic number *(OL(3)) of OL(3). They showed that 4 ≤x~*(OL(3))≤16. We present an algorithm that colors every on-line-3-chromatic graph with 4 colors. Thus x*(OL(3)) = 4.