Conflict-Free Colouring of Graphs

Glebov, Roman and Szabó, Tibor and Tardos, Gábor (2013) Conflict-Free Colouring of Graphs. COMBINATORICS PROBABILITY AND COMPUTING, &. pp. 1-15. ISSN 0963-5483

Preview

Text 1111.5501.pdf Download (230kB) | Preview

Abstract

We study the conflict-free chromatic number χ CF of graphs from extremal and probabilistic points of view. We resolve a question of Pach and Tardos about the maximum conflict-free chromatic number an n-vertex graph can have. Our construction is randomized. In relation to this we study the evolution of the conflict-free chromatic number of the Erdo{double acute}s-Rényi random graph G(n,p) and give the asymptotics for p = ω(1/n). We also show that for p ≥ 1/2 the conflict-free chromatic number differs from the domination number by at most 3. Copyright © Cambridge University Press 2013.

Actions (login required)

Edit Item