EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Coloring triangle‐free graphs with local list sizes

Ewan Davies, Rémi de Joannis de Verclos, Ross J Kang, François Pirot

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.

AbstractSchlagwörterBibliografische AngabenZitierenVerwandte Studien

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

hard‐core modellist coloringtriangle‐free graphs

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}
}
Kostenlos starten →