On-line coloring \(k\)-colorable graphs
type: Item
instance of: scholarly article
title: On-line coloring \(k\)-colorable graphs
zbMATH Open document ID: 0908.05043
DOI: 10.1007/BF02780324
published in: Israel Journal of Mathematics
publication date: 1999-03-18T00:00:00Z
review text: In this paper it is shown that for any \(k\), there exists an on-line algorithm that will colour any \(k\)-colourable graph on \(n\) vertices with \(O(n^{1-1/k!})\) colours, improving the previous bound of \(O(n\log^{(2k- 3)}n/\log^{(2k- 4)}n)\). For \(k= 3\) and \(k= 4\) it is possible to do even better.
Mathematics Subject Classification ID: 05C15
zbMATH DE Number: 1195643
zbMATH Keywords: coloring
zbMATH Keywords: on-line algorithm
author: H. A. Kierstead
reviewed by: Chris Jagger
MaRDI profile type: Publication
cites work: New approximation algorithms for graph coloring
cites work: An \(\tilde{O}(n^{3/14})\)-coloring algorithm for 3-colorable graphs
cites work: On-line coloring of perfect graphs
cites work: Q4276003
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/bf02780324
OpenAlex ID: W2012000897
description: scientific article; zbMATH DE number 1195643