Coloring random graphs online without creating monochromatic subgraphs

DOI10.1002/rsa.20445zbMath1296.05077arXiv1103.5849OpenAlexW2163914211MaRDI QIDQ5495876

Thomas Rast, Torsten Mütze, Reto Spöhel

Publication date: 7 August 2014

Published in: Random Structures & Algorithms (Search for Journal in Brave)

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

zbMATH Keywords

random graphRamsey propertyonline process

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Coloring of graphs and hypergraphs (05C15) Generalized Ramsey theory (05C55) Online algorithms; streaming algorithms (68W27)

Related Items (2)

Proper colouring painter-builder game ⋮ Tight Bounds for Online Vector Scheduling

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Online vertex-coloring games in random graphs
• On-line Ramsey theory for bounded degree graphs
• Online Ramsey games for triangles in random graphs
• Ramsey properties of random graphs
• There is no fast method for finding monochromatic complete subgraphs
• On-line Ramsey theory
• Equitable coloring of random graphs
• On-line Ramsey Numbers
• On the strong chromatic number of random graphs
• Upper Bounds for Online Ramsey Games in Random Graphs
• Online Ramsey Games in Random Graphs
• The t-Improper Chromatic Number of Random Graphs
• Threshold functions for small subgraphs
• Globally sparse vertex‐ramsey graphs
• Sharp thresholds for certain Ramsey properties of random graphs
• Ramsey Games Against a One-Armed Bandit
• Hunting for sharp thresholds
• Probabilistic One-Player Ramsey Games via Deterministic Two-Player Games
• Two variants of the size Ramsey number

This page was built for publication: Coloring random graphs online without creating monochromatic subgraphs