On-line coloring of perfect graphs
type: Item
instance of: scholarly article
title: On-line coloring of perfect graphs
zbMATH Open document ID: 0881.68087
DOI: 10.1007/BF01271267
published in: Combinatorica
publication date: 1998-01-11T00:00:00Z
review text: An algorithm is presented which colors on-line \(k\)-colorable perfect graphs with \(n^{10/\log\log n}\) colors. By modifying Vishwanathan's construction a \(\bigl(\log_3 n\bigr)^{k-1}/2^k k^{k-1}\) lower bound is given.
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 05C15
zbMATH DE Number: 1102604
zbMATH Keywords: on-line coloring
zbMATH Keywords: perfect graphs=20
author: H. A. Kierstead
author: Katalin Kolossa
reviewed by: Péter Komjáth
MaRDI profile type: Publication
cites work: Effective coloration
cites work: On-line and first fit colorings of graphs
cites work: The Linearity of First-Fit Coloring of Interval Graphs
cites work: On-Line and First-fit Coloring of Graphs that Do Not Induce $P_5 $
cites work: On-Line Coloring and Recursive Graph Theory
cites work: Q3950561
cites work: An on-line graph coloring algorithm with sublinear performance ratio
cites work: Randomized online graph coloring
full work available at URL: https://doi.org/10.1007/bf01271267
OpenAlex ID: W1983054380
description: scientific article; zbMATH DE number 1102604