Enregistré dans:
| Auteur principal: | |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | https://arxiv.org/abs/2403.12302 |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866914198514040832 |
|---|---|
| author | Deniz, Zakir |
| author_facet | Deniz, Zakir |
| contents | A vertex coloring of a graph $G$ is called a $2$-distance coloring if any two vertices at a distance at most $2$ from each other receive different colors. Recently, Bousquet et al. (Discrete Mathematics, 346(4), 113288, 2023) proved that $2Δ+7$ colors are sufficient for the $2$-distance coloring of planar graphs with maximum degree $Δ\geq 9$. In this paper, we strengthen their result by removing the maximum degree constraint and show that all planar graphs admit a 2-distance $(2Δ+7)$-coloring. This particularly improves the result of Van den Heuvel and McGuinness (Journal of Graph Theory, 42(2), 110-124, 2003). |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2403_12302 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A 2-distance $(2Δ+7)$-coloring of planar graphs Deniz, Zakir Combinatorics A vertex coloring of a graph $G$ is called a $2$-distance coloring if any two vertices at a distance at most $2$ from each other receive different colors. Recently, Bousquet et al. (Discrete Mathematics, 346(4), 113288, 2023) proved that $2Δ+7$ colors are sufficient for the $2$-distance coloring of planar graphs with maximum degree $Δ\geq 9$. In this paper, we strengthen their result by removing the maximum degree constraint and show that all planar graphs admit a 2-distance $(2Δ+7)$-coloring. This particularly improves the result of Van den Heuvel and McGuinness (Journal of Graph Theory, 42(2), 110-124, 2003). |
| title | A 2-distance $(2Δ+7)$-coloring of planar graphs |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2403.12302 |