@article{MTMT:2516369,
	title = {Conflict-Free Colouring of Graphs},
	url = {https://m2.mtmt.hu/api/publication/2516369},
	author = {GLEBOV, R and SZABÓ, T and Tardos, Gábor},
	doi = {10.1017/S0963548313000540},
	journal-iso = {COMB PROBAB COMPUT},
	journal = {COMBINATORICS PROBABILITY & COMPUTING},
	volume = {23},
	unique-id = {2516369},
	issn = {0963-5483},
	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 Erdo{double acute}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. Copyright © Cambridge University Press 2013.},
	keywords = {05C80; Secondary 05C35; 2010 Mathematics subject classification: Primary 05C15; 05D40; 05C69},
	year = {2014},
	eissn = {1469-2163},
	pages = {434-448}
}

@article{MTMT:169428,
	title = {Conflict-free colourings of graphs and hypergraphs},
	url = {https://m2.mtmt.hu/api/publication/169428},
	author = {Pach, János and Tardos, Gábor},
	doi = {10.1017/S0963548309990290},
	journal-iso = {COMB PROBAB COMPUT},
	journal = {COMBINATORICS PROBABILITY & COMPUTING},
	volume = {18},
	unique-id = {169428},
	issn = {0963-5483},
	abstract = {A colouring of the vertices of a hypergraph H is called conflict-free if each hyperedge E of H contains a vertex of 'unique' colour that does not get repeated in E. The smallest number of colours required for such a colouring is called the conflict-free chromatic number of H, and is denoted by chi(CF)(H). This parameter wits first introduced by Even, Lotker, Ron and Smorodinsky (FOCS 2002) in a geometric setting, in connection with frequency assignment problems for cellular networks. Here we analyse this notion for general hypergraphs. It is shown that chi(CF)(H) <= 1/2 + root 2m + 1/4, for every hypergraph with tit edges, and that this bound is tight. Better bounds of the order of tit 1 It log tit are proved under the assumption that the size of every edge of H is at least 2t - 1, for some t >= 3. Using Lovasz's Local Lemma, the same result holds for hypergraphs in which the size of every edge is at least 2t - 1 and every edge intersects at most tit others. We give efficient polynomial-time algorithms to obtain such colourings.
		
		Our machinery can also be applied to the hypergraphs induced by the neighbourhoods of the vertices of a graph. It turns out that in this case we need far fewer colours. For example, it is shown that the vertices of any graph G with maximum degree Delta can be coloured with log(2+is an element of)Delta colours, so that the neighbourhood of every vertex contains a point of 'unique' colour. We give an efficient deterministic algorithm to find such a colouring, based oil a randomized algorithmic version of the Lovasz Local Lemma, suggested by Beck, Molloy and Reed. To achieve this, we need to (1) correct a small error in the Molloy-Reed approach, (2) restate and re-prove their result in a deterministic form.},
	year = {2009},
	eissn = {1469-2163},
	pages = {819-834}
}