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....
Autores principales: | , , , |
---|---|
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 |