On-line coloring \(k\)-colorable graphs

DOI10.1007/BF02780324zbMath0908.05043OpenAlexW2012000897MaRDI QIDQ1264277

Henry A. Kierstead

Publication date: 18 March 1999

Published in: Israel Journal of Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf02780324

zbMATH Keywords

on-line algorithmcoloring

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Related Items (23)

On the performance of the first-fit coloring algorithm on permutation graphs ⋮ Lower Bounds for On-line Graph Colorings ⋮ Obtaining online ecological colourings by generalizing first-fit ⋮ Graphs are not universal for online computability ⋮ Primitive recursive reverse mathematics ⋮ A structure of punctual dimension two ⋮ Graph coloring with rejection ⋮ Online edge coloring of paths and trees with a fixed number of colors ⋮ Online presentations of finitely generated structures ⋮ Circumference, chromatic number and online coloring ⋮ Online coloring of hypergraphs ⋮ Minimum order of graphs with given coloring parameters ⋮ First-fit coloring of \(\{P_{5},K_{4}-e\}\)-free graphs ⋮ Online coloring graphs with high girth and high odd girth ⋮ Online hypergraph coloring ⋮ Online chromatic number is PSPACE-complete ⋮ Online coloring and a new type of adversary for online graph problems ⋮ Online coloring a token graph ⋮ FOUNDATIONS OF ONLINE STRUCTURE THEORY ⋮ Open Problems on Graph Coloring for Special Graph Classes ⋮ Tight Bounds for Online Coloring of Basic Graph Classes ⋮ Online independent sets. ⋮ Online coloring and a new type of adversary for online graph problems

Cites Work

• Unnamed Item
• An \(\tilde{O}(n^{3/14})\)-coloring algorithm for 3-colorable graphs
• An on-line graph coloring algorithm with sublinear performance ratio
• On-line coloring of perfect graphs
• Randomized online graph coloring
• New approximation algorithms for graph coloring

This page was built for publication: On-line coloring \(k\)-colorable graphs