Tight Bounds for Online Coloring of Basic Graph Classes
From MaRDI portal
Publication:5111690
DOI10.4230/LIPIcs.ESA.2017.7zbMath1442.68159OpenAlexW2964175068MaRDI QIDQ5111690
Susanne Albers, Sebastian Schraink
Publication date: 27 May 2020
Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2017/7826/pdf/LIPIcs-ESA-2017-7.pdf/
Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20) Online algorithms; streaming algorithms (68W27)
Related Items (3)
The power of amortized recourse for online graph problems ⋮ Batch coloring of graphs ⋮ Online coloring and a new type of adversary for online graph problems
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Online coloring of bipartite graphs with and without advice
- Online promise problems with online width metrics
- Characterizations of strongly chordal graphs
- An on-line graph coloring algorithm with sublinear performance ratio
- On-line coloring \(k\)-colorable graphs
- On the power of randomization in on-line algorithms
- Coloring inductive graphs on-line
- Lower bounds for on-line graph coloring
- On-line coloring of geometric intersection graphs
- A tight bound for online colouring of disk graphs
- Online Graph Coloring with Advice and Randomized Adversary
- The Power of Reordering for Online Minimum Makespan Scheduling
- On-line and first fit colorings of graphs
- Randomized online graph coloring
- Effective coloration
- Parallel and On-Line Graph Coloring
- Online Conflict-Free Colouring for Hypergraphs
- Deterministic conflict-free coloring for intervals
- Independence and Coloring Problems on Intersection Graphs of Disks
This page was built for publication: Tight Bounds for Online Coloring of Basic Graph Classes
