Online coloring and a new type of adversary for online graph problems

DOI10.1007/s00453-021-00920-wOpenAlexW3026866611MaRDI QIDQ5970811

Yaqiao Li, Denis Pankratov, Vishnu V. Narayan

Publication date: 3 May 2022

Published in: Algorithmica (Search for Journal in Brave)

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

zbMATH Keywords

connected componentsonline algorithmsonline coloringCBIPFirstFitparametrized analysis

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Graph theory (05Cxx)

Cites Work

• Online coloring of bipartite graphs with and without advice
• An on-line graph coloring algorithm with sublinear performance ratio
• On-line coloring \(k\)-colorable graphs
• A partial k-arboretum of graphs with bounded treewidth
• Lower bounds for on-line graph coloring
• Tight bounds for online coloring of basic graph classes
• Lower Bounds for On-line Graph Colorings
• Emergence of Scaling in Random Networks
• On-line and first fit colorings of graphs
• Randomized online graph coloring
• Effective coloration
• Networks

This page was built for publication: Online coloring and a new type of adversary for online graph problems