Cliques, Chromatic Number, and Independent Sets in the Semi-random Process

arXiv2303.13443MaRDI QIDQ6430635FDOQ6430635

Authors: David Gamarnik, Mihyun Kang, Paweł Prałat 

Publication date: 23 March 2023

Abstract: The semi-random graph process is a single player game in which the player is initially presented an empty graph on $n$ vertices. In each round, a vertex $u$ is presented to the player independently and uniformly at random. The player then adaptively selects a vertex $v$, and adds the edge $uv$ to the graph. For a fixed monotone graph property, the objective of the player is to force the graph to satisfy this property with high probability in as few rounds as possible. In this paper, we investigate the following three properties: containing a complete graph of order $k$, having the chromatic number at least $k$, and not having an independent set of size at least $k$.

This page was built for publication: Cliques, Chromatic Number, and Independent Sets in the Semi-random Process

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6430635)