Lower Bounds for On-line Graph Colorings

DOI10.1007/978-3-319-13075-0_40zbMath1435.05141arXiv1404.7259OpenAlexW3098594656MaRDI QIDQ2942655

Xuding Zhu, Grzegorz Gutowski, Piotr Micek, Jakub Kozik

Publication date: 11 September 2015

Published in: Algorithms and Computation (Search for Journal in Brave)

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

zbMATH Keywords

online graph coloring games

Mathematics Subject Classification ID

Games involving graphs (91A43) Coloring of graphs and hypergraphs (05C15) Games on graphs (graph-theoretic aspects) (05C57)

Related Items (6)

An On-line Competitive Algorithm for Coloring $$P_8$$-free Bipartite Graphs ⋮ Colouring bottomless rectangles and arborescences ⋮ Online coloring of short intervals ⋮ An on-line competitive algorithm for coloring bipartite graphs without long induced paths ⋮ Online coloring and a new type of adversary for online graph problems ⋮ Online coloring and a new type of adversary for online graph problems

Cites Work

• Unnamed Item
• Online coloring of bipartite graphs with and without advice
• An on-line graph coloring algorithm with sublinear performance ratio
• A note on Ramsey numbers
• On-line coloring \(k\)-colorable graphs
• On the minimal number of edges in color-critical graphs
• The independence number of graphs with large odd girth
• Circumference, chromatic number and online coloring
• On-Line Coloring and Recursive Graph Theory
• The Ramsey number R(3, t) has order of magnitude t²/log t
• On-Line and First-fit Coloring of Graphs that Do Not Induce $P_5 $

This page was built for publication: Lower Bounds for On-line Graph Colorings