论文标题
韦格纳平面图的放松最高度4
Relaxation of Wegner's Planar Graph Conjecture for maximum degree 4
论文作者
论文摘要
著名的韦格纳（Wegner）的平面图猜想在平面图$ g $的平方$ g^2 $的色度上宣称上限紧密，具体取决于最高度$δ（g）$ $ g $。猜想解决的唯一情况是，托马森（Thomassen）证明了$δ（g）= 3 $，而Hartke，Jahanbekam和Thomas则独立。对于$δ（g）= 4 $，韦格纳的平面图猜想指出，$ g^2 $的色数最多是9；即使是这个案例，也仍然广泛开放，最近Bousquet，de Meyer，Deschamps和Pierron声称上限为12。 我们采用了一种完全不同的方法，并表明可以通过$δ（g）= 4 $的平面图$ g $的正方形放松，可以通过9种颜色来实现。我们没有要求顶点附近的每种颜色都是唯一的，这相当于$ g^2 $的适当着色，而是寻求$ g $的适当着色，以便最多可以在4级的顶点的附近重复一种颜色，但没有其他地方。
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 $Δ(G)$ of $G$. The only case that the conjecture is resolved is when $Δ(G)=3$, which was proven to be true by Thomassen, and independently by Hartke, Jahanbekam, and Thomas. For $Δ(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 $Δ(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.
