Colorability Saturation Games

We consider the following two-player game: Maxi and Mini start with the empty graph on \(n\) vertices and take turns, always adding one additional edge to the graph such that the chromatic number is at most \(k\), where \(k \in \mathbb{N}\) is a given parameter. The game is over when the graph is sa...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2018-02
Main Author: Keusch, Ralph
Format: Article
Language:English
Subjects:
Apexes
Combinatorial analysis
Game theory
Games
Graph theory
Saturation (color)
Upper bounds
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We consider the following two-player game: Maxi and Mini start with the empty graph on \(n\) vertices and take turns, always adding one additional edge to the graph such that the chromatic number is at most \(k\), where \(k \in \mathbb{N}\) is a given parameter. The game is over when the graph is saturated and no further edge can be inserted. Maxi wants to maximize the length of the game while Mini wants to minimize it. The score \(s(n,\chi_{>k})\) denotes the number of edges in the final graph, given that both players followed an optimal strategy. This colorability game belongs to the family of \emph{saturation games} that are known to provide beautiful and challenging problems despite being defined via simple combinatorial rules. The analysis of colorability saturation games has been initiated recently by Hefetz, Krivelevich, Naor, and Stojaković (2016). In this paper, we improve their results by providing almost matching lower and upper bounds on the score of the game that hold for arbitrary choices of \(k\) and \(n>k\). In addition, we study the specific game with \(k=4\) in more details and prove that its score is \(n^2/3+O(n)\).
ISSN:2331-8422