Coloring triangle‐free graphs with local list sizes
Random Structures & Algorithms · 2020-10 · 57 (3) · 730-744
DOI: 10.1002/rsa.20945 ↗Kurz gefasst
Fachartikel in der Zeitschrift Random Structures & Algorithms, online erschienen am 13.07.2020. Verfasst von Ewan Davies und 3 weiteren Autor:innen. Beteiligte Einrichtung: Korteweg-De Vries Institute for Mathematics University of Amsterdam Amsterdam Netherlands. Die Arbeit wurde bisher 15-mal zitiert (Crossref) und nennt 17 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: European Research Council under the European Union's Seventh Framework Programme, European Research Council Nederlandse Organisatie voor Wetenschappelijk Onderzoek ERC Grant, Vidi Grant of the Netherlands Organisation for Scientific Research.
Abstract (Originalsprache)
We prove two distinct and natural refinements of a recent breakthrough result of Molloy (and a follow‐up work of Bernshteyn) on the (list) chromatic number of triangle‐free graphs. In both our results, we permit the amount of color made available to vertices of lower degree to be accordingly lower. One result concerns list coloring and correspondence coloring, while the other concerns fractional coloring. Our proof of the second illustrates the use of the hard‐core model to prove a Johansson‐type result, which may be of independent interest.
Schlagwörter
Stichwörter der Autor:innen
Autor:innen und Institutionen
- Korteweg-De Vries Institute for Mathematics University of Amsterdam Amsterdam Netherlands.
- Department of Mathematics Radboud University Nijmegen Nijmegen Netherlands.
- LORIA, Université de Lorraine Nancy France.
Förderung
- European Research Council under the European Union's Seventh Framework Programme
- European Research Council Nederlandse Organisatie voor Wetenschappelijk Onderzoek ERC Grant
- Vidi Grant of the Netherlands Organisation for Scientific Research
Zitieren
APA
Davies, E., de Joannis de Verclos, R., Kang, R. J., & Pirot, F. (2020). Coloring triangle‐free graphs with local list sizes. Random Structures & Algorithms, 57(3), 730-744. https://doi.org/10.1002/rsa.20945
Vancouver
Davies E, de Joannis de Verclos R, Kang RJ, Pirot F. Coloring triangle‐free graphs with local list sizes. Random Structures & Algorithms. 2020;57(3):730-744. doi:10.1002/rsa.20945
BibTeX
@article{Davies2020,
author = {Davies, Ewan and de Joannis de Verclos, Rémi and Kang, Ross J and Pirot, François},
title = {Coloring triangle‐free graphs with local list sizes},
journal = {Random Structures & Algorithms},
year = {2020},
volume = {57},
number = {3},
pages = {730--744},
doi = {10.1002/rsa.20945}
}
EUVIMED