Tight bounds for online coloring of basic graph classes

DOI10.1007/S00453-020-00759-7MaRDI QIDQ2223701zbMATH OpenOpenAlexFDO

Authors Susanne Albers, Sebastian Schraink

Publication date 1 February 2021

Published in Algorithmica (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/1702.07172

zbMATH Keywords

randomizationonline algorithmslower boundsgraph coloring

Mathematics Subject Classification ID

Online algorithms; streaming algorithms (68W27) Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Coloring of graphs and hypergraphs (05C15)

Recommendations

• Tight bounds for online coloring of basic graph classes
• scientific article; zbMATH DE number 65708
• Lower bounds for on-line graph coloring
• Coloring inductive graphs on-line
• Randomized online graph coloring

Cites work

• scientific article; zbMATH DE number 3769624 (Why is no real title available?)
• scientific article; zbMATH DE number 566078 (Why is no real title available?)
• A Constant Factor Approximation Algorithm for Reordering Buffer Management
• A tight bound for online colouring of disk graphs
• An improved competitive algorithm for reordering buffer management
• An on-line graph coloring algorithm with sublinear performance ratio
• Batch coloring of graphs
• Characterizations of strongly chordal graphs
• Coloring inductive graphs on-line
• Deterministic conflict-free coloring for intervals: from offline to online
• Effective coloration
• Independence and Coloring Problems on Intersection Graphs of Disks
• Lower bounds for on-line graph coloring
• On the power of randomization in on-line algorithms
• On-line and first fit colorings of graphs
• On-line coloring of geometric intersection graphs
• Online coloring of bipartite graphs with and without advice
• Online conflict-free colouring for hypergraphs
• Online graph coloring against a randomized adversary
• Online graph coloring with advice and randomized adversary (extended abstract)
• Online promise problems with online width metrics
• Parallel and On-Line Graph Coloring
• Randomized online graph coloring
• The Power of Reordering for Online Minimum Makespan Scheduling

Cited in

(16)

• Online Bounded Coloring of Permutation and Overlap Graphs
• Tight bounds for online coloring of basic graph classes
• Structural Information and Communication Complexity
• scientific article; zbMATH DE number 742967 (Why is no real title available?)
• Bounded families for the on-line \(t\)-relaxed coloring
• Online coloring and a new type of adversary for online graph problems
• A refined analysis of online path coloring in trees
• Online coloring of short intervals
• Online dominating set and coloring
• A tight bound for online colouring of disk graphs
• Online coloring known graphs
• Parameterized and Exact Computation
• Coloring inductive graphs on-line
• Max-coloring and online coloring with bandwidths on interval graphs
• scientific article; zbMATH DE number 65708 (Why is no real title available?)
• Batch coloring of graphs

This page was built for publication: Tight bounds for online coloring of basic graph classes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2223701)