Skip to content Skip to navigation
University of Warwick
  • Study
  • |
  • Research
  • |
  • Business
  • |
  • Alumni
  • |
  • News
  • |
  • About

University of Warwick
Publications service & WRAP

Highlight your research

  • WRAP
    • Home
    • Search WRAP
    • Browse by Warwick Author
    • Browse WRAP by Year
    • Browse WRAP by Subject
    • Browse WRAP by Department
    • Browse WRAP by Funder
    • Browse Theses by Department
  • Publications Service
    • Home
    • Search Publications Service
    • Browse by Warwick Author
    • Browse Publications service by Year
    • Browse Publications service by Subject
    • Browse Publications service by Department
    • Browse Publications service by Funder
  • Help & Advice
University of Warwick

The Library

  • Login
  • Admin

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:
  • ArXiv
Official URL: http://dx.doi.org/10.1017/S0963548313000540

Request Changes to record.

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:
DateEvent
May 2014Published
29 November 2013Available
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:
  • ArXiv

Request changes or add full text files to a record

Repository staff actions (login required)

View Item View Item
twitter

Email us: wrap@warwick.ac.uk
Contact Details
About Us