تقرير
Relaxation of Wegner's Planar Graph Conjecture for maximum degree 4
| العنوان: | Relaxation of Wegner's Planar Graph Conjecture for maximum degree 4 |
|---|---|
| المؤلفون: | Cho, Eun-Kyung, Choi, Ilkyoo, Lidický, Bernard |
| سنة النشر: | 2022 |
| المجموعة: | Mathematics |
| مصطلحات موضوعية: | Mathematics - Combinatorics |
| الوصف: | The famous Wegner's Planar Graph Conjecture asserts tight upper bounds on the chromatic number of the square $G^2$ of a planar graph $G$, depending on the maximum degree $\Delta(G)$ of $G$. The only case that the conjecture is resolved is when $\Delta(G)=3$, which was proven to be true by Thomassen, and independently by Hartke, Jahanbekam, and Thomas. For $\Delta(G)=4$, Wegner's Planar Graph Conjecture states that the chromatic number of $G^2$ is at most 9; even this case is still widely open, and very recently Bousquet, de Meyer, Deschamps, and Pierron claimed an upper bound of 12. We take a completely different approach, and show that a relaxation of properly coloring the square of a planar graph $G$ with $\Delta(G)=4$ can be achieved with 9 colors. Instead of requiring every color in the neighborhood of a vertex to be unique, which is equivalent to a proper coloring of $G^2$, we seek a proper coloring of $G$ such that at most one color is allowed to be repeated in the neighborhood of a vertex of degree 4, but nowhere else. Comment: 9 pages |
| نوع الوثيقة: | Working Paper |
| الوصول الحر: | http://arxiv.org/abs/2212.10643Test |
| رقم الانضمام: | edsarx.2212.10643 |
| قاعدة البيانات: | arXiv |
| الوصف غير متاح. |