Name
Abstract | ||
|---|---|---|
We study the conflict-free chromatic number chi 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 Erdos-Renyi 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 differs from the domination number by at most 3. |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1017/S0963548313000540 | COMBINATORICS PROBABILITY & COMPUTING |
DocType | Volume | Issue |
Journal | 23 | 3 |
ISSN | Citations | PageRank |
0963-5483 | 3 | 0.41 |
References | Authors | |
4 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Roman Glebov | 1 | 53 | 9.26 |
| Tibor Szabó | 2 | 420 | 45.51 |
| Gábor Tardos | 3 | 1261 | 140.58 |