The Library
Conflict-free colouring of graphs
Tools
Tools
Tools
Glebov, Roman, Szabó, Tibor and Tardos, Gábor (2014) Conflict-free colouring of graphs. Combinatorics, Probability and Computing, Volume 23 (Number 3). pp. 434-448. doi:10.1017/S0963548313000540
An open access version can be found in:
Official URL: http://dx.doi.org/10.1017/S0963548313000540
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 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.
| Item Type: | Journal Article | ||||||
|---|---|---|---|---|---|---|---|
| Divisions: | Faculty of Science > Mathematics | ||||||
| Journal or Publication Title: | Combinatorics, Probability and Computing | ||||||
| Publisher: | Cambridge University Press | ||||||
| ISSN: | 0963-5483 | ||||||
| Official Date: | May 2014 | ||||||
| Dates: |
|
||||||
| Volume: | Volume 23 | ||||||
| Number: | Number 3 | ||||||
| Page Range: | pp. 434-448 | ||||||
| DOI: | 10.1017/S0963548313000540 | ||||||
| Status: | Peer Reviewed | ||||||
| Publication Status: | Published | ||||||
| Access rights to Published version: | Restricted or Subscription Access | ||||||
| Open Access Version: |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
