Planar Graphs with $\Delta\ge 9$ are Entirely $(\Delta+2)$-Colorable
| Autor: | Yiqiao Wang, Weifan Wang, Xiaoxue Hu |
|---|---|
| Rok vydání: | 2014 |
| Předmět: | |
| Zdroj: | SIAM Journal on Discrete Mathematics. 28:1892-1905 |
| ISSN: | 1095-7146 0895-4801 |
| DOI: | 10.1137/130938992 |
| Popis: | A plane graph $G$ is entirely $k$-colorable if $V(G)\cup E(G) \cup F(G)$ can be colored with $k$ colors such that any two adjacent or incident elements receive different colors. In 1993, Borodin proved that every plane graph $G$ with maximum degree $\Delta\ge 12$ is entirely $(\Delta+2)$-colorable. In this paper, we improve this result by showing that every plane graph $G$ with $\Delta\ge 9$ is entirely $(\Delta+2)$-colorable. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|