On the on-line chromatic number of the family of on-line 3-chromatic graphs (Q1916112)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On the on-line chromatic number of the family of on-line 3-chromatic graphs |
scientific article |
Statements
On the on-line chromatic number of the family of on-line 3-chromatic graphs (English)
0 references
24 September 1997
0 references
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\).
0 references
on-line colouring
0 references
chomatic number
0 references