Combinatorics Seminar

When: Sunday, January 22, 10am Where: Schreiber 309 Speaker: Roman Glebov, Free University of Berlin Title: Conflict-free coloring of graphs

Abstract:

When talking about coloring a graph, the by far most studied notion is the proper coloring, that is, a coloring of the vertex set such that the color of each vertex is unique in the vertex's closed neighborhood. We study a generalization of this concept, calling a coloring conflict-free if the closed neighborhood of each vertex contains a vertex with a color that is unique there.

We study the conflict-free chromatic number chi_{CF} of graphs from the 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 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>=1/2 the conflict-free chromatic number typically differs from the domination number by at most 3.

Joint work with Tibor Szabó and Gábor Tardos.