https://m2.mtmt.hu/ hun 2026-08-26 06:22 JournalArticle 169428 VALIDATED true 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 0 2018-09-12T12:19:44.000+0000 false 169428 2026-05-21T07:38:59.462+0000 2024-10-30T10:38:23.778+0000 2010-08-13T19:09:29.000+0000 true 10002598 Pach János /api/author/10002598 Author true 10002598 2026-04-01T11:25:52.763+0000 2026-04-01T11:25:52.763+0000 2024-10-30T10:38:27.173+0000 true 10073918 Kovács Marcell /api/admin/10073918 Admin true Admin 10073918 /api/admin/10073918 Kovács Marcell true true Admin 10067876 /api/admin/10067876 Ladányi Gusztáv true true 2024-10-17T15:54:52.719+0000 true false true 24 24 /api/publicationtype/24 PublicationType 1 true 24 JournalArticle true 10000059 Article true 24 24 /api/publicationtype/24 PublicationType 1 true 24 JournalArticle /api/subtype/10000059 Szakcikk SubType 101 true 10000059 true 1 /api/category/1 Category true 1 Pach, J Conflict-free colourings of graphs and hypergraphs true true /api/journal/27782 REVIEWED true false 27782 false 27782 true 0963-5483 1469-2163 Journal FOREIGN 18 5 819 834 819 16 2009 true 330690 /api/conference/330690 true 10901 true 10017 /api/country/10017 Country true 13 /api/city/10901 City true 1412707 Conference true 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. 2010 352760 true true true true true false GREEN GREEN 2026-05-21 true https://www.math.nyu.edu/~pach/publications/ConflictFreeGraph052909.pdf true 10015168 Szakonyi Erzsebet /api/admin/10015168 Admin true 10015168 101 0 87 85 7 86 86 76 84 86 86 84 84 98 3 0 100 97 87 85 0 4 4 Folyóiratcikk Journal Article 24 60 Könyvrészlet Chapter in Book 25 26 Könyv Book 23 0 Egyéb konferenciaközlemény Conference paper 31 1 Egyéb konferenciakötet Conference proceedings 32 0 Oltalmi formák Protection forms 26 0 Disszertáció Thesis 28 6 Egyéb Miscellaneous 29 7 Alkotás Achievement 22 0 Kutatási adat Research data 33 0 Folyóiratcikk Journal Article 24 0 0 0 Könyvrészlet Chapter in Book 25 0 0 0 Könyv Book 23 0 0 0 Egyéb konferenciaközlemény Conference paper 31 0 0 0 Egyéb konferenciakötet Conference proceedings 32 0 0 0 Oltalmi formák Protection forms 26 0 0 0 Disszertáció Thesis 28 0 0 0 Egyéb Miscellaneous 29 0 0 0 Alkotás Achievement 22 0 0 0 Kutatási adat Research data 33 0 0 0 2009 0 2 2 2 2 2010 0 4 3 3 2 2011 0 5 4 5 4 2012 0 8 8 8 8 2013 0 3 3 3 3 2014 0 2 1 2 1 2015 0 5 5 5 5 2016 0 2 2 2 2 2017 0 5 5 5 5 2018 0 10 10 10 10 2019 0 4 4 4 4 2020 0 7 7 7 7 2021 0 9 9 9 9 2022 0 6 6 6 6 2023 0 5 5 5 5 2024 0 11 11 11 11 2025 0 12 12 12 12 2026 0 1 1 1 1 D1 true false false false 2012-11-13T13:04:55.000+0000 2012-07-02T10:44:41.000+0000 Diszkrét Matematika (RAMKI); Geometria (HRN RAMKI) 2 8 2 2 0 true 10073918 10067876 Language 10002 /api/language/10002 Angol English true 2 true PersonAuthorship 224774 /api/authorship/224774 1 0.5 true false Author 10002598 /api/author/10002598 Pach János true 10002598 true Pach J true false false AuthorshipType 1 /api/authorshiptype/1 0 true 0 true false 327172 true PersonAuthorship 224775 /api/authorship/224775 2 0.5 false true Author 10009673 /api/author/10009673 Tardos Gábor true 10009673 true Tardos G true false false AuthorshipType 1 /api/authorshiptype/1 0 true 0 true false 327171 true PublicationIdentifier 82124 /api/publicationidentifier/82124 PlainSource 6 /api/publicationsource/6 PublicationSourceType 10001 /api/publicationsourcetype/10001 true true true DOI DOI https://doi.org/@@@ true true 6 true false IDENTICAL 10.1017/S0963548309990290 https://doi.org/10.1017/S0963548309990290 false 36523 true PublicationIdentifier 82122 /api/publicationidentifier/82122 PlainSource 1 /api/publicationsource/1 PublicationSourceType 10003 /api/publicationsourcetype/10003 false true true WoS WoS https://www.webofscience.com/wos/woscc/full-record/@@@ true true 1 true false IDENTICAL 000269984900014 https://www.webofscience.com/wos/woscc/full-record/000269984900014 false 36524 true PublicationIdentifier 82123 /api/publicationidentifier/82123 PlainSource 3 /api/publicationsource/3 PublicationSourceType 10003 /api/publicationsourcetype/10003 false true true Scopus Scopus http://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-@@@ true true 3 true false IDENTICAL 74049160755 http://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-74049160755 false 36525 true PublicationIdentifier 82127 /api/publicationidentifier/82127 PlainSource 39 /api/publicationsource/39 PublicationSourceType 10006 /api/publicationsourcetype/10006 true true true Teljes dokumentum Full text @@@ true true 39 true GREEN true NO https://www.math.nyu.edu/~pach/publications/ConflictFreeGraph052909.pdf https://www.math.nyu.edu/~pach/publications/ConflictFreeGraph052909.pdf false 36526 true PublicationIdentifier 82125 /api/publicationidentifier/82125 PlainSource 7 /api/publicationsource/7 PublicationSourceType 10003 /api/publicationsourcetype/10003 false true true Mathematical Reviews Mathematical Reviews https://mathscinet.ams.org/mathscinet-getitem?mr=@@@ true true 7 true false NO MR2534271 https://mathscinet.ams.org/mathscinet-getitem?mr=MR2534271 false 1817636 true PublicationIdentifier 82126 /api/publicationidentifier/82126 PlainSource 12 /api/publicationsource/12 PublicationSourceType 10003 /api/publicationsourcetype/10003 false true true Google scholar http://scholar.Google.com/scholar?hl=en&lr=&cluster=@@@ true true 12 true false NO 4045855522799326780 http://scholar.Google.com/scholar?hl=en&lr=&cluster=4045855522799326780 false 595528 true PublicationIdentifier 14858901 /api/publicationidentifier/14858901 PlainSource 13 /api/publicationsource/13 PublicationSourceType 10003 /api/publicationsourcetype/10003 false true true Google scholar hash Google scholar hash http://scholar.Google.com/scholar?hl=en&lr=&cluster=@@@ true true 13 true NO PJYBgSnEJTgJ http://scholar.Google.com/scholar?hl=en&lr=&cluster=PJYBgSnEJTgJ false 10306113 true Classification 10018 /api/classification/10018 true true Classification 10010 /api/classification/10010 true true Classification 10003 /api/classification/10003 true true Classification 10034 /api/classification/10034 true true Classification 10002 /api/classification/10002 true true SjrRating 5804880 /api/sjrrating/5804880 10 0.1 journal RatingType 10002 /api/ratingtype/10002 sjr true true ClassificationExternal 2614 /api/classificationexternal/2614 true 2614 true D1 DIRECT true 5804880 true /api/publication/169428 <div class="JournalArticle Publication long-list"> <div class="authors"> <img title="Forrásközlemény" style="float: left" src="/frontend/resources/grid/publication-core-icon.png"> <img title="Idézőközlemény" style="float: left" src="/frontend/resources/grid/publication-citation-icon.png"> <div class="autype autype0"> <span class="author-name" mtid="10002598"><a href="/gui2/?type=authors&mode=browse&sel=10002598" target="_blank">Pach J (<span class="authorship-author-name">Pach János</span> <span class="authorAux-mtmt"> Diszkrét és algoritmikus geometria, kombinatorika</span>) </a> </span> <span class="author-affil"><span title="MTA Rényi Alfréd Matematikai Kutatóintézet">MTA RAMKI</span>/Geometria</span> ;&nbsp;&nbsp;&nbsp; <span class="author-name" mtid="10009673"><a href="/gui2/?type=authors&mode=browse&sel=10009673" target="_blank">Tardos G (<span class="authorship-author-name">Tardos Gábor</span> <span class="authorAux-mtmt"> Kombinatorika</span>) </a> </span> <span class="author-affil"><span title="MTA Rényi Alfréd Matematikai Kutatóintézet">MTA RAMKI</span>/Diszkrét Matematika</span> </div> </div> <div class="title"><a href="/gui2/?mode=browse&params=publication;169428" target="_blank">Conflict-free colourings of graphs and hypergraphs</a></div> <div> <span class="journal-title">COMBINATORICS PROBABILITY & COMPUTING</span> <span class="journal-issn">(<a target="_blank" href="https://portal.issn.org/resource/ISSN/0963-5483">0963-5483</a> <a target="_blank" href="https://portal.issn.org/resource/ISSN/1469-2163">1469-2163</a>)</span>: <span class="journal-volume">18</span> <span class="journal-issue">5</span> <span class="page"> pp 819-834 </span> <span class="year">(2009)</span> <div class="conference"> Conference on New Directions in Algorithms, Combinatorics and Optimization held in honor of Tom Trotter. Konferencia helye, ideje: <span class="location">Atlanta, Amerikai Egyesült Államok <span class="conference-date">2008.05.05. - 2008.05.09.</span> </div> </div> <div class="pub-footer"> <span class="language" xmlns="http://www.w3.org/1999/html">Nyelv: Angol | </span> <span class="identifiers"> <span class="id identifier oa_none" title="none"> <a style="color:blue" title="10.1017/S0963548309990290" target="_blank" href="https://doi.org/10.1017/S0963548309990290"> DOI </a> </span> <span class="id identifier oa_none" title="none"> <a style="color:blue" title="000269984900014" target="_blank" href="https://www.webofscience.com/wos/woscc/full-record/000269984900014"> WoS </a> </span> <span class="id identifier oa_none" title="none"> <a style="color:blue" title="74049160755" target="_blank" href="http://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-74049160755"> Scopus </a> </span> <span class="id identifier oa_GREEN" title=" Green "> <a style="color:black" title="https://www.math.nyu.edu/~pach/publications/ConflictFreeGraph052909.pdf" target="_blank" href="https://www.math.nyu.edu/~pach/publications/ConflictFreeGraph052909.pdf"> Teljes dokumentum </a> </span> <span class="id identifier oa_none" title="none"> <a style="color:black" title="MR2534271" target="_blank" href="https://mathscinet.ams.org/mathscinet-getitem?mr=MR2534271"> Mathematical Reviews </a> </span> <span class="id identifier oa_none" title="none"> <a style="color:black" title="4045855522799326780" target="_blank" href="http://scholar.Google.com/scholar?hl=en&lr=&cluster=4045855522799326780"> Google scholar </a> </span> <span class="id identifier oa_none" title="none"> <a style="color:black" title="PJYBgSnEJTgJ" target="_blank" href="http://scholar.Google.com/scholar?hl=en&lr=&cluster=PJYBgSnEJTgJ"> Google scholar hash </a> </span> </span> <OnlyViewableByAuthor><div class="ratings"> <div class="journal-subject">Folyóirat szakterülete: Scopus - Theoretical Computer Science&nbsp;&nbsp;&nbsp;SJR indikátor:&nbsp;D1</div> <div class="journal-subject">Folyóirat szakterülete: Scopus - Applied Mathematics&nbsp;&nbsp;&nbsp;SJR indikátor:&nbsp;Q1</div> <div class="journal-subject">Folyóirat szakterülete: Scopus - Computational Theory and Mathematics&nbsp;&nbsp;&nbsp;SJR indikátor:&nbsp;Q1</div> <div class="journal-subject">Folyóirat szakterülete: Scopus - Statistics and Probability&nbsp;&nbsp;&nbsp;SJR indikátor:&nbsp;Q1</div> </div></OnlyViewableByAuthor> <div class="publication-citation" style="margin-left: 0.5cm;"> <span title="Nyilvános idézőközlemények összesen, említések nélkül" class="citingPub-count">Nyilvános idéző összesen: 100</span> | Független: 97 | Függő: 3 | Nem jelölt: 0 | WoS jelölt: 76 | Scopus jelölt:&nbsp;84 | WoS/Scopus jelölt:&nbsp;86 | DOI jelölt:&nbsp;86 </div> <div class="publication-citation" style="margin-left: 0.5cm; margin-top:0"> <span title="Nyilvános idézéskapcsolatok száma (egy közleményen belüli többszörös említésekkel együtt)" class="citingPub-count">Nyilvános idéző+említés összesen: 101</span> | Független: 98 | Függő: 3 | Nem jelölt: 0 </div> <div class="publication-citation"> <a target="_blank" href="/api/publication?cond=citations.related;eq;169428&sort=publishedYear,desc&sort=title"> Idézett közlemények száma: 4 </a> </div> <div class="mtid"><span class="long-pub-mtid">Közlemény: 169428</span> | <span class="status-data status-VALIDATED"> Egyeztetett </span> <span class="oldId">Régi azonosító: 169428</span> | Forrás Idéző | <span class="type-subtype">Folyóiratcikk ( Szakcikk ) </span> | <span class="pub-category">Tudományos</span> | <span class="publication-sourceOfData">kézi felvitel</span> </div> <div class="lastModified">Utolsó módosítás: 2024.10.30. 11:38 Kovács Marcell (MTMT Közp., admin) </div> <div class="lockedBy">Központi kezelésű 2024.10.17. 17:54 Kovács Marcell (MTMT Közp., admin) Ladányi Gusztáv (MTMT API user, admin) </div> <pre class="comment" style="margin-top: 0; margin-bottom: 0;"><u>Megjegyzés</u>: Megjegyzés-22475611 N1 <a href="http://scholar.google.com/scholar?cluster=4045855522799326780" hash="PJYBgSnEJTgJ" target="_new">Google scholar link</a> 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 Unive...</pre> </div></div>