Planar graphs without cycles of length 4 or 5 are $(7m:2m)$-DP-colorable
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915621734711296 |
|---|---|
| author | Xu, Xiaoyan Zhu, Xuding |
| author_facet | Xu, Xiaoyan Zhu, Xuding |
| contents | It was conjectured by Steinberg in 1976 that planar graphs without cycles of length 4 or 5 are 3-colorable. This conjecture attracted a substantial amount of attention and was finally refuted by Cohen-Addad, Hebdige, Král', Li and Salgado in 2017. Although Steinberg's conjecture is settled, coloring of this family of graphs, as well as some other families of planar graphs forbidding certain cycle lengths have been attracting a lot of recent attention and many challenging problems remain open. One problem of interest is multiple coloring and multiple list coloring of this family of graphs. It was proved by Dvǒrák and Hu that
planar graphs without cycles of length 4 or 5 are $(11,3)$-colorable, and this result was improved by Wang, who proved that graphs in this family are $(7:2)$-colorable. On the other hand, it was proved by Xu and Zhu that for every positive integer $m$, there is a graph in this family which is not $(3m + \lfloor \frac{m-1}{12} \rfloor, m)$-choosable.
In this paper, we prove that for any positive integer $m$, graphs in this family are $(7m:2m)$-DP-colorable, and hence $(7m,2m)$-choosable. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_12914 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Planar graphs without cycles of length 4 or 5 are $(7m:2m)$-DP-colorable Xu, Xiaoyan Zhu, Xuding Combinatorics It was conjectured by Steinberg in 1976 that planar graphs without cycles of length 4 or 5 are 3-colorable. This conjecture attracted a substantial amount of attention and was finally refuted by Cohen-Addad, Hebdige, Král', Li and Salgado in 2017. Although Steinberg's conjecture is settled, coloring of this family of graphs, as well as some other families of planar graphs forbidding certain cycle lengths have been attracting a lot of recent attention and many challenging problems remain open. One problem of interest is multiple coloring and multiple list coloring of this family of graphs. It was proved by Dvǒrák and Hu that planar graphs without cycles of length 4 or 5 are $(11,3)$-colorable, and this result was improved by Wang, who proved that graphs in this family are $(7:2)$-colorable. On the other hand, it was proved by Xu and Zhu that for every positive integer $m$, there is a graph in this family which is not $(3m + \lfloor \frac{m-1}{12} \rfloor, m)$-choosable. In this paper, we prove that for any positive integer $m$, graphs in this family are $(7m:2m)$-DP-colorable, and hence $(7m,2m)$-choosable. |
| title | Planar graphs without cycles of length 4 or 5 are $(7m:2m)$-DP-colorable |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2511.12914 |