We study the conflict-free chromatic number χ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ő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.
Glebov et al. REF extend this from an extremal and probabilistic point of view by proving that almost all G(n, p)-graphs have conflict-free chromatic number O(log n) for p ∈ ω(1/n), and by giving a randomized construction for graphs having conflict-free chromatic number Θ(log 2 n).
Conflict-free coloring of graphs
arXiv: Combinatorics
Mathematics