https://m2.mtmt.hu/ hun 2026-08-25 09:34 JournalArticle 2516369 VALIDATED true 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 0 2017-01-13T18:51:56.000+0000 false 2516369 2026-05-16T04:19:40.874+0000 2024-10-31T09:04:26.668+0000 2014-01-30T14:39:32.000+0000 true 10009673 Tardos Gábor /api/author/10009673 Author true 10009673 2024-10-31T09:04:21.048+0000 2024-10-31T09:04:21.048+0000 2024-10-31T09:04:26.808+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 GLEBOV, R Conflict-Free Colouring of Graphs true true /api/journal/27782 REVIEWED true false 27782 false 27782 true 0963-5483 1469-2163 Journal FOREIGN 23 3 434 448 434 15 2014 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. 2014 719999 true true true false true false GREEN GREEN 2026-05-16 true http://real.mtak.hu/10035 true 10015168 Szakonyi Erzsebet /api/admin/10015168 Admin true 10015168 29 0 29 29 0 29 29 25 28 29 29 29 29 29 0 0 29 29 29 29 0 1 1 Folyóiratcikk Journal Article 24 22 Könyvrészlet Chapter in Book 25 6 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 0 Egyéb Miscellaneous 29 0 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 2015 0 2 2 2 2 2016 0 0 0 0 0 2017 0 3 3 3 3 2018 0 4 4 4 4 2019 0 1 1 1 1 2020 0 1 1 1 1 2021 0 5 5 5 5 2022 0 2 2 2 2 2023 0 2 2 2 2 2024 0 5 5 5 5 2025 0 3 3 3 3 2026 0 1 1 1 1 Q1 false false false false 2015-02-04T11:40:00.000+0000 2014-01-30T14:47:37.000+0000 Diszkrét Matematika (RAMKI) 1 7 1 3 0 true 10073918 10067876 Language 10002 /api/language/10002 Angol English true 2 true PersonAuthorship 4937702 /api/authorship/4937702 1 0.33333334 true false GLEBOV R true false false AuthorshipType 1 /api/authorshiptype/1 0 true 0 true false 19330861 true PersonAuthorship 4937703 /api/authorship/4937703 2 0.33333334 false false SZABÓ T true false false AuthorshipType 1 /api/authorshiptype/1 0 true 0 true false 19330860 true PersonAuthorship 4937704 /api/authorship/4937704 3 0.33333334 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 19330859 true PublicationIdentifier 768178 /api/publicationidentifier/768178 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/S0963548313000540 https://doi.org/10.1017/S0963548313000540 false 606613 true PublicationIdentifier 768179 /api/publicationidentifier/768179 SwordSource 36 /api/publicationsource/36 PublicationSourceType 10007 /api/publicationsourcetype/10007 true true true REAL REAL http://real.mtak.hu/@@@ true true 36 true GREEN true IDENTICAL 10035 http://real.mtak.hu/10035 false 617009 true PublicationIdentifier 768176 /api/publicationidentifier/768176 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 000338294000006 https://www.webofscience.com/wos/woscc/full-record/000338294000006 false 1509179 true PublicationIdentifier 768177 /api/publicationidentifier/768177 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 84898023633 http://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-84898023633 false 606612 true PublicationIdentifier 14859178 /api/publicationidentifier/14859178 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 NO MR3189420 https://mathscinet.ams.org/mathscinet-getitem?mr=MR3189420 false 18026605 true PublicationIdentifier 14859179 /api/publicationidentifier/14859179 PlainSource 37 /api/publicationsource/37 PublicationSourceType 10007 /api/publicationsourcetype/10007 true true true arXiv http://arxiv.org/abs/@@@ true true 37 true 1111.5501 http://arxiv.org/abs/1111.5501 false 18026606 true Classification 10003 /api/classification/10003 true true Classification 10034 /api/classification/10034 true true Keyword 1260243 /api/keyword/1260243 true 1260243 true Keyword 1350316 /api/keyword/1350316 true 1350316 true Keyword 1350317 /api/keyword/1350317 true 1350317 true Keyword 1350318 /api/keyword/1350318 true 1350318 true Keyword 1350319 /api/keyword/1350319 true 1350319 true SjrRating 11060547 /api/sjrrating/11060547 75 0.24 journal RatingType 10002 /api/ratingtype/10002 sjr true true ClassificationExternal 2604 /api/classificationexternal/2604 true 2604 true Q1 DIRECT true true Reference 1786041 /api/reference/1786041 1 false true Reference 1786042 /api/reference/1786042 2 false true Reference 1786043 /api/reference/1786043 3 false true Reference 1786044 /api/reference/1786044 4 false true Reference 1786045 /api/reference/1786045 5 false true Reference 1786046 /api/reference/1786046 6 false true Reference 1786047 /api/reference/1786047 7 false true Reference 1786048 /api/reference/1786048 8 false true Reference 1786049 /api/reference/1786049 9 false true Reference 1786050 /api/reference/1786050 10 false true Reference 1786051 /api/reference/1786051 11 false true /api/publication/2516369 <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" >GLEBOV R </span> ;&nbsp;&nbsp;&nbsp; <span class="author-name" >SZABÓ T </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;2516369" target="_blank">Conflict-Free Colouring of Graphs</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">23</span> <span class="journal-issue">3</span> <span class="page"> pp 434-448 </span> <span class="year">(2014)</span> </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/S0963548313000540" target="_blank" href="https://doi.org/10.1017/S0963548313000540"> DOI </a> </span> <span class="id identifier oa_GREEN" title=" Green "> <a style="color:blue" title="10035" target="_blank" href="http://real.mtak.hu/10035"> REAL </a> </span> <span class="id identifier oa_none" title="none"> <a style="color:blue" title="000338294000006" target="_blank" href="https://www.webofscience.com/wos/woscc/full-record/000338294000006"> WoS </a> </span> <span class="id identifier oa_none" title="none"> <a style="color:blue" title="84898023633" target="_blank" href="http://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-84898023633"> Scopus </a> </span> <span class="id identifier oa_none" title="none"> <a style="color:black" title="MR3189420" target="_blank" href="https://mathscinet.ams.org/mathscinet-getitem?mr=MR3189420"> Mathematical Reviews </a> </span> <span class="id identifier oa_none" title="none"> <a style="color:black" title="1111.5501" target="_blank" href="http://arxiv.org/abs/1111.5501"> arXiv </a> </span> </span> <OnlyViewableByAuthor><div class="ratings"> <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 class="journal-subject">Folyóirat szakterülete: Scopus - Theoretical Computer Science&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: 29</span> | Független: 29 | Függő: 0 | Nem jelölt: 0 | WoS jelölt: 25 | Scopus jelölt:&nbsp;28 | WoS/Scopus jelölt:&nbsp;29 | DOI jelölt:&nbsp;29 </div> <div class="publication-citation"> <a target="_blank" href="/api/publication?cond=citations.related;eq;2516369&sort=publishedYear,desc&sort=title"> Idézett közlemények száma: 1 </a> </div> <div class="mtid"><span class="long-pub-mtid">Közlemény: 2516369</span> | <span class="status-data status-VALIDATED"> Egyeztetett </span> <span class="oldId">Régi azonosító: 2516369</span> | Forrás Idéző | <span class="type-subtype">Folyóiratcikk ( Szakcikk ) </span> | <span class="pub-category">Tudományos</span> | <span class="publication-sourceOfData">Scopus</span> </div> <div class="lastModified">Utolsó módosítás: 2024.10.31. 10:04 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>: 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 ...</pre> </div></div>