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

DOI10.1016/0012-365X(95)00189-4MaRDI QIDQ1916112zbMATH OpenFDO

Authors Katalin Kolossa

Publication date 24 September 1997

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0012-365X(95)00189-4

zbMATH Keywords

chomatic numberon-line colouring

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Review text

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\).

Recommendations

• On-line 3-chromatic graphs. II: Critical graphs
• scientific article; zbMATH DE number 4170931
• scientific article; zbMATH DE number 65699
• On-line coloring \(k\)-colorable graphs

Cites work

• An on-line graph coloring algorithm with sublinear performance ratio
• scientific article; zbMATH DE number 3891425 (Why is no real title available?)
• scientific article; zbMATH DE number 4170931 (Why is no real title available?)
• scientific article; zbMATH DE number 3769624 (Why is no real title available?)
• scientific article; zbMATH DE number 65699 (Why is no real title available?)
• scientific article; zbMATH DE number 524128 (Why is no real title available?)
• On-Line 3-Chromatic Graphs I. Triangle-Free Graphs
• On-line 3-chromatic graphs. II: Critical graphs
• On-line and first fit colorings of graphs
• On-Line and First-fit Coloring of Graphs that Do Not Induce $P_5 $
• On-Line Coloring and Recursive Graph Theory
• Randomized online graph coloring
• The Linearity of First-Fit Coloring of Interval Graphs

Cited in

(3)

• On-line 3-chromatic graphs. II: Critical graphs
• On-Line 3-Chromatic Graphs I. Triangle-Free Graphs
• Online coloring graphs with high girth and high odd girth

This page was built for publication: On the on-line chromatic number of the family of on-line 3-chromatic graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1916112)