2022/12/20 by Cho, Eun-Kyung, Choi, Ilkyoo, Lidický, Bernard
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2212.10643
The famous Wegner's Planar Graph Conjecture asserts tight upper bounds on the chromatic number of the square G2 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 G2 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 G2, 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.