B-colorings of planar and outerplanar graphs
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866915470537392128 |
|---|---|
| author | Martin, Ryan R. Ruszinkó, Miklós Sárközy, Gábor N. |
| author_facet | Martin, Ryan R. Ruszinkó, Miklós Sárközy, Gábor N. |
| contents | A coloring of the edges of a graph $G$ in which every $K_{1,2}$ is totally multicolored is known as a proper coloring and a coloring of the edges of $G$ in which every $K_{1,2}$ and every $K_{2,2}$ is totally multicolored is called a B-coloring.
In this paper, we establish that a planar graph with maximum degree $Δ$ can be B-colored with $\max\{2Δ,32\}$ colors. This is best-possible for large $Δ$ because $K_{2,Δ}$ requires $2Δ$ colors. In addition, there is an example with $Δ=4$ that requires $12$ colors.
We also establish that an outerplanar graph with maximum degree $Δ$ can be B-colored with $\max\{Δ,6\}$ colors. This is almost best-possible because $Δ$ colors are necessary and there is an example with $Δ=4$ that requires $5$ colors. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2408_09081 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | B-colorings of planar and outerplanar graphs Martin, Ryan R. Ruszinkó, Miklós Sárközy, Gábor N. Combinatorics 05C15, 05C10, 05C35 A coloring of the edges of a graph $G$ in which every $K_{1,2}$ is totally multicolored is known as a proper coloring and a coloring of the edges of $G$ in which every $K_{1,2}$ and every $K_{2,2}$ is totally multicolored is called a B-coloring. In this paper, we establish that a planar graph with maximum degree $Δ$ can be B-colored with $\max\{2Δ,32\}$ colors. This is best-possible for large $Δ$ because $K_{2,Δ}$ requires $2Δ$ colors. In addition, there is an example with $Δ=4$ that requires $12$ colors. We also establish that an outerplanar graph with maximum degree $Δ$ can be B-colored with $\max\{Δ,6\}$ colors. This is almost best-possible because $Δ$ colors are necessary and there is an example with $Δ=4$ that requires $5$ colors. |
| title | B-colorings of planar and outerplanar graphs |
| topic | Combinatorics 05C15, 05C10, 05C35 |
| url | https://arxiv.org/abs/2408.09081 |