Online coloring known graphs
type: Item
instance of: scholarly article
title: Online coloring known graphs
zbMATH Open document ID: 0940.05030
author: Magnús M. Halldórsson
published in: The Electronic Journal of Combinatorics
publication date: 2000-03-12T00:00:00Z
full work available at URL: https://eudml.org/doc/120387
full work available at URL: v7i1r7.html
review text: Summary: The problem of online coloring an unknown graph is known to be hard. Here we consider the problem of online coloring in the relaxed situation where the input must be isomorphic to a given known graph. All that foils a computationally powerful player is that it is not known to which sections of the graph the vertices to be colored belong. We show that the performance ratio of any online coloring algorithm with advance knowledge of the input graph is at least \(\Omega(N/\log^2N)\), where \(N\) is the number of vertices. This matches and generalizes the bound for the case of an unknown input graph. We also show that any online independent set algorithm has a performance ratio at least \(N/8\).
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 68W25
zbMATH DE Number: 1413183
zbMATH Keywords: graph coloring
zbMATH Keywords: online algorithms
zbMATH Keywords: online coloring
zbMATH Keywords: performance ratio
zbMATH Keywords: online independent set algorithm
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 1413183