Randomized online graph coloring

DOI10.1016/0196-6774(92)90061-GzbMath0768.68185OpenAlexW2084263468MaRDI QIDQ4015271

Sundar Vishwanathan

Publication date: 12 January 1993

Published in: Journal of Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0196-6774(92)90061-g

zbMATH Keywords

lower boundchromatic numberpolynomial timerandomized online algorithmonline graph coloring algorithm

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (17)

Lower bounds for on-line graph coloring ⋮ Online Graph Coloring Against a Randomized Adversary ⋮ Adding isolated vertices makes some greedy online algorithms optimal ⋮ On the on-line chromatic number of the family of on-line 3-chromatic graphs ⋮ On-line coloring of perfect graphs ⋮ Selection of programme slots of television channels for giving advertisement: a graph theoretic approach ⋮ Impartial coloring games ⋮ THE GRAPH-BIN PACKING PROBLEM ⋮ Tight bounds for online coloring of basic graph classes ⋮ Online coloring of bipartite graphs with and without advice ⋮ Online coloring graphs with high girth and high odd girth ⋮ Online hypergraph coloring ⋮ Dynamic graph coloring ⋮ On-line coloring \(k\)-colorable graphs ⋮ Tight Bounds for Online Coloring of Basic Graph Classes ⋮ Online coloring and a new type of adversary for online graph problems ⋮ Coloring inductive graphs on-line

This page was built for publication: Randomized online graph coloring