Proper edge colorings of planar graphs with rainbow $C_4$-s
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908510193713152 |
|---|---|
| author | Gyárfás, András Martin, Ryan R. Ruszinkó, Miklós Sárközy, Gábor N. |
| author_facet | Gyárfás, András Martin, Ryan R. Ruszinkó, Miklós Sárközy, Gábor N. |
| contents | We call a proper edge coloring of a graph $G$ a B-coloring if every 4-cycle of $G$ is colored with four different colors. Let $q_B(G)$ denote the smallest number of colors needed for a B-coloring of $G$. Motivated by earlier papers on B-colorings, here we consider $q_B(G)$ for planar and outerplanar graphs in terms of the maximum degree $Δ= Δ(G)$. We prove that $q_B(G)\le 2Δ+8$ for planar graphs, $q_B(G)\le 2Δ$ for bipartite planar graphs and $q_B(G)\le Δ+1$ for outerplanar graphs with $Δ\ge 4$. We conjecture that, for $Δ$ sufficiently large, $q_B(G)\le 2Δ(G)$ for planar $G$ and $q_B(G)\le Δ(G)$ for outerplanar $G$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2408_09059 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Proper edge colorings of planar graphs with rainbow $C_4$-s Gyárfás, András Martin, Ryan R. Ruszinkó, Miklós Sárközy, Gábor N. Combinatorics We call a proper edge coloring of a graph $G$ a B-coloring if every 4-cycle of $G$ is colored with four different colors. Let $q_B(G)$ denote the smallest number of colors needed for a B-coloring of $G$. Motivated by earlier papers on B-colorings, here we consider $q_B(G)$ for planar and outerplanar graphs in terms of the maximum degree $Δ= Δ(G)$. We prove that $q_B(G)\le 2Δ+8$ for planar graphs, $q_B(G)\le 2Δ$ for bipartite planar graphs and $q_B(G)\le Δ+1$ for outerplanar graphs with $Δ\ge 4$. We conjecture that, for $Δ$ sufficiently large, $q_B(G)\le 2Δ(G)$ for planar $G$ and $q_B(G)\le Δ(G)$ for outerplanar $G$. |
| title | Proper edge colorings of planar graphs with rainbow $C_4$-s |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2408.09059 |