TY - JOUR AU - GLEBOV, R AU - SZABÓ, T AU - Tardos, Gábor TI - Conflict-Free Colouring of Graphs JF - COMBINATORICS PROBABILITY & COMPUTING J2 - COMB PROBAB COMPUT VL - 23 PY - 2014 IS - 3 SP - 434 EP - 448 PG - 15 SN - 0963-5483 DO - 10.1017/S0963548313000540 UR - https://m2.mtmt.hu/api/publication/2516369 ID - 2516369 N1 - Department of Mathematics, ETH, 8092 Zurich, Switzerland Mathematics Institute, DIMAP, University of Warwick, Coventry CV4 7AL, United Kingdom Institute of Mathematics, Free University of Berlin, 14195 Berlin, Germany Alfréd Rényi Institute of Mathematics, Hungarian Academy of Sciences, Budapest, Hungary Zhejiang Normal University, Jinhua, China Cited By :18 Export Date: 19 January 2023 AB - 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. LA - English DB - MTMT ER - TY - JOUR AU - Pach, János AU - Tardos, Gábor TI - Conflict-free colourings of graphs and hypergraphs JF - COMBINATORICS PROBABILITY & COMPUTING J2 - COMB PROBAB COMPUT VL - 18 PY - 2009 IS - 5 SP - 819 EP - 834 PG - 16 SN - 0963-5483 DO - 10.1017/S0963548309990290 UR - https://m2.mtmt.hu/api/publication/169428 ID - 169428 N1 - Megjegyzés-22475611 N1 Google scholar link EPFL-SB-IMB-DCG, CH-1015 Lausanne, Switzerland Department of Computer Science, City College, 138th Street at Convent Avenue, NY 10031, United States School of Computing Science, Simon Fraser University, 8888 University Drive, Burnaby, BC V5A 1S6, Canada Rnyi Institute, 1315 Reltanoda utca Budapest, Hungary Cited By :46 Export Date: 20 September 2021 Correspondence Address: Pach, J.; EPFL-SB-IMB-DCG, CH-1015 Lausanne, Switzerland; email: pach@cims.nyu.edu AB - 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. LA - English DB - MTMT ER -