An improved bound for 2-distance coloring of planar graphs with girth six
Fuente:
arXiv
Salvato in:
| Autore principale: | |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2022
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866911111691894784 |
|---|---|
| author | Deniz, Zakir |
| author_facet | Deniz, Zakir |
| contents | A vertex coloring of a graph $G$ is said to be a 2-distance coloring if any two vertices at distance at most $2$ from each other receive different colors, and the least number of colors for which $G$ admits a $2$-distance coloring is known as the $2$-distance chromatic number $χ_2(G)$ of $G$. When $G$ is a planar graph with girth at least $6$ and maximum degree $Δ\geq 6$, we prove that $χ_2(G)\leq Δ+4$. This improves the best-known bound for 2-distance coloring of planar graphs with girth six. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2212_03831 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | An improved bound for 2-distance coloring of planar graphs with girth six Deniz, Zakir Combinatorics 05C15, 05C10, 05C12 G.2.2 A vertex coloring of a graph $G$ is said to be a 2-distance coloring if any two vertices at distance at most $2$ from each other receive different colors, and the least number of colors for which $G$ admits a $2$-distance coloring is known as the $2$-distance chromatic number $χ_2(G)$ of $G$. When $G$ is a planar graph with girth at least $6$ and maximum degree $Δ\geq 6$, we prove that $χ_2(G)\leq Δ+4$. This improves the best-known bound for 2-distance coloring of planar graphs with girth six. |
| title | An improved bound for 2-distance coloring of planar graphs with girth six |
| topic | Combinatorics 05C15, 05C10, 05C12 G.2.2 |
| url | https://arxiv.org/abs/2212.03831 |