Coloring squares of planar graphs with girth six

• DOI: 10.1016/j.ejc.2007.11.005
• Publication Date: 2008-03-06T23:37:19Z
• Authors: Zdeněk Dvořák; Daniel Král’; Pavel Nejedlý; Riste Škrekovski
• Keywords: Girth (graph theory); Square (algebra); Degree (music)

AbstractWang and Lih conjectured that for every g≥5, there exists a number M(g) such that the square of a planar graph G of girth at least g and maximum degree Δ≥M(g) is (Δ+1)-colorable. The conjecture is known to be true for g≥7 but false for g∈{5,6}. We show that the conjecture for g=6 is off by just one, i.e., the square of a planar graph G of girth at least six and sufficiently large maximum degree is (Δ+2)-colorable.