On the computational complexity and strategies of online Ramsey theory

DOI10.1016/J.ENDM.2015.06.099zbMath1346.05187OpenAlexW2175554205WikidataQ57937802 ScholiaQ57937802MaRDI QIDQ322363

Pavel Dvořák, Tomáš Valla

Publication date: 14 October 2016

Full work available at URL: https://doi.org/10.1016/j.endm.2015.06.099

zbMATH Keywords

complexitystrategyonline Ramsey game

Mathematics Subject Classification ID

Hypergraphs (05C65) Games involving graphs (91A43) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Ramsey theory (05D10) Games on graphs (graph-theoretic aspects) (05C57)

Related Items (1)

Online chromatic number is PSPACE-complete

Cites Work

• Online Ramsey theory for planar graphs
• On-line Ramsey theory for bounded degree graphs
• Trees with an on-line degree Ramsey number of four
• On-line Ramsey theory
• Coloring number and on-line Ramsey theory for graphs and hypergraphs
• On-line Ramsey Numbers
• Ramsey Games Against a One-Armed Bandit
• Graph Ramsey theory and the polynomial hierarchy
• Unnamed Item

This page was built for publication: On the computational complexity and strategies of online Ramsey theory