On-line Ramsey theory
type: Item
instance of: scholarly article
title: On-line Ramsey theory
zbMATH Open document ID: 1057.05058
author: J. A. Grytczuk
author: Mariusz Hałuszczak
author: H. A. Kierstead
published in: The Electronic Journal of Combinatorics
publication date: 2004-10-13T00:00:00Z
full work available at URL: https://eudml.org/doc/124260
full work available at URL: v11i1r57.html
review text: Summary: The Ramsey game we consider in this paper is played on an unbounded set of vertices by two players, called Builder and Painter. In one move Builder introduces a new edge and Painter paints it red or blue. The goal of Builder is to force Painter to create a monochromatic copy of a fixed target graph \(H\), keeping the constructed graph in a prescribed class \({\mathcal G}\). The main problem is to recognize the winner for a given pair \(H,{\mathcal G}\). In particular, we prove that Builder has a winning strategy for any \(k\)-colorable graph \(H\) in the game played on \(k\)-colorable graphs. Another class of graphs with this strange self-unavoidability property is the class of forests. We show that the class of outerplanar graphs does not have this property. The question of whether planar graphs are self-unavoidable is left open. We also consider a multicolor version of Ramsey on-line game. To extend our main result for 3-colorable graphs we introduce another Ramsey type game, which seems interesting in its own right.
Mathematics Subject Classification ID: 05C55
Mathematics Subject Classification ID: 05C38
Mathematics Subject Classification ID: 15A15
Mathematics Subject Classification ID: 05A15
Mathematics Subject Classification ID: 15A18
Mathematics Subject Classification ID: 05D10
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 91A43
zbMATH DE Number: 2107499
zbMATH Keywords: Ramsey game
zbMATH Keywords: \(k\)-colorable graph
zbMATH Keywords: Ramsey on-line game
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 2107499