Lower bounds for on-line graph coloring

DOI10.1016/0304-3975(94)90157-0zbMath0822.68081OpenAlexW2033961412MaRDI QIDQ1331951

Mario Szegedy, Magnús M. Halldórsson

Publication date: 29 August 1994

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(94)90157-0

zbMATH Keywords

randomized algorithmsvertex-coloring graphs

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)

Related Items (21)

Online selection of intervals and \(t\)-intervals ⋮ Competitive vertex recoloring. (Online disengagement) ⋮ Colouring bottomless rectangles and arborescences ⋮ The advice complexity of a class of hard online problems ⋮ Online coloring of short intervals ⋮ Lower Bounds for On-line Interval Coloring with Vector and Cardinality Constraints ⋮ Batch Coloring of Graphs ⋮ Unnamed Item ⋮ Tight Bounds for Online Vector Scheduling ⋮ Non-clairvoyant scheduling with conflicts for unit-size jobs ⋮ Online coloring of hypergraphs ⋮ Tight bounds for online coloring of basic graph classes ⋮ Batch coloring of graphs ⋮ On-line vertex-covering ⋮ On-line maximum-order induced hereditary subgraph problems ⋮ Dynamic graph coloring ⋮ Online chromatic number is PSPACE-complete ⋮ Online coloring a token graph ⋮ 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
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A dynamic location problem for graphs
• An on-line graph coloring algorithm with sublinear performance ratio
• Online matching with blocked input
• Competitive algorithms for server problems
• Smallest-last ordering and clustering and graph coloring algorithms
• On-line and first fit colorings of graphs
• Randomized online graph coloring
• Worst-Case Performance Bounds for Simple One-Dimensional Packing Algorithms
• Effective coloration

This page was built for publication: Lower bounds for on-line graph coloring