Cargando…

Coloring triangle‐free graphs with local list sizes

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....

Descripción completa

Detalles Bibliográficos
Autores principales: Davies, Ewan, de Joannis de Verclos, Rémi, Kang, Ross J., Pirot, François
Formato: Online Artículo Texto
Lenguaje:English
Publicado: John Wiley & Sons, Inc. 2020
Materias:
Acceso en línea:https://www.ncbi.nlm.nih.gov/pmc/articles/PMC7508179/
https://www.ncbi.nlm.nih.gov/pubmed/32999582
http://dx.doi.org/10.1002/rsa.20945
_version_ 1783585380646256640
author Davies, Ewan
de Joannis de Verclos, Rémi
Kang, Ross J.
Pirot, François
author_facet Davies, Ewan
de Joannis de Verclos, Rémi
Kang, Ross J.
Pirot, François
author_sort Davies, Ewan
collection PubMed
description 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.
format Online
Article
Text
id pubmed-7508179
institution National Center for Biotechnology Information
language English
publishDate 2020
publisher John Wiley & Sons, Inc.
record_format MEDLINE/PubMed
spelling pubmed-75081792020-09-28 Coloring triangle‐free graphs with local list sizes Davies, Ewan de Joannis de Verclos, Rémi Kang, Ross J. Pirot, François Random Struct Algorithms Research Articles 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. John Wiley & Sons, Inc. 2020-07-13 2020-10 /pmc/articles/PMC7508179/ /pubmed/32999582 http://dx.doi.org/10.1002/rsa.20945 Text en © The Authors. Random Structures and Algorithms published by Wiley Periodicals LLC. This is an open access article under the terms of the http://creativecommons.org/licenses/by/4.0/ License, which permits use, distribution and reproduction in any medium, provided the original work is properly cited.
spellingShingle Research Articles
Davies, Ewan
de Joannis de Verclos, Rémi
Kang, Ross J.
Pirot, François
Coloring triangle‐free graphs with local list sizes
title Coloring triangle‐free graphs with local list sizes
title_full Coloring triangle‐free graphs with local list sizes
title_fullStr Coloring triangle‐free graphs with local list sizes
title_full_unstemmed Coloring triangle‐free graphs with local list sizes
title_short Coloring triangle‐free graphs with local list sizes
title_sort coloring triangle‐free graphs with local list sizes
topic Research Articles
url https://www.ncbi.nlm.nih.gov/pmc/articles/PMC7508179/
https://www.ncbi.nlm.nih.gov/pubmed/32999582
http://dx.doi.org/10.1002/rsa.20945
work_keys_str_mv AT daviesewan coloringtrianglefreegraphswithlocallistsizes
AT dejoannisdeverclosremi coloringtrianglefreegraphswithlocallistsizes
AT kangrossj coloringtrianglefreegraphswithlocallistsizes
AT pirotfrancois coloringtrianglefreegraphswithlocallistsizes