dc.contributor.author
Glebov, Roman
dc.contributor.author
Szabó, Tibor
dc.contributor.author
Tardos, Gábor
dc.date.accessioned
2018-06-08T03:06:24Z
dc.date.available
2015-09-17T10:54:00.398Z
dc.identifier.uri
https://refubium.fu-berlin.de/handle/fub188/14513
dc.identifier.uri
http://dx.doi.org/10.17169/refubium-18705
dc.description.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.
en
dc.rights.uri
http://journals.cambridge.org/action/displaySpecialPage?pageId=4608
dc.subject.ddc
500 Naturwissenschaften und Mathematik::510 Mathematik
dc.title
Conflict-Free Colouring of Graphs
dc.type
Wissenschaftlicher Artikel
dcterms.bibliographicCitation
Combinatorics, Probability and Computing. - 23 (2014), 3, S. 434-448
dcterms.bibliographicCitation.doi
10.1017/S0963548313000540
dcterms.bibliographicCitation.url
http://dx.doi.org/10.1017/S0963548313000540
refubium.affiliation
Mathematik und Informatik
de
refubium.mycore.fudocsId
FUDOCS_document_000000023120
refubium.resourceType.isindependentpub
no
refubium.mycore.derivateId
FUDOCS_derivate_000000005406
dcterms.accessRights.openaire
open access
