A bound on the chromatic number of the square of a planar graph

Wegner conjectured that the chromatic number of the square of any planar graph G with maximum degree Δ⩾8 is bounded by χ(G2)⩽⌊32Δ⌋+1. We prove the bound χ(G2)⩽⌈53Δ⌉+78. This is asymptotically an improvement on the previously best-known bound. For large values of Δ we give the bound of χ(G2)⩽⌈53Δ⌉+25. We generalize this result to L(p,q)-labeling of planar graphs, by showing that λqp(G)⩽q⌈53Δ⌉+18p+77q-18. For each of the results, the proof provides a quadratic time algorithm.