Conflict-free coloring of graphs

Roman Glebov, Tibor Szabó, Gábor Tardos

Published 2011-11-23, updated 2013-09-19Version 2

We study the conflict-free chromatic number chi_{CF} of graphs from extremal and probabilistic point 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 Erd\H{o}s-R\'enyi random graph G(n,p) and give the asymptotics for p=omega(1/n). We also show that for p \geq 1/2 the conflict-free chromatic number differs from the domination number by at most 3.