A bound on the chromatic number of the square of a planar graph (Q2485944)

The well-known Wegner conjecture says that \(\chi(G^2)\leq \lceil{3\over 2}\Delta\rceil+ 1\), where \(G^2\) is the square of graph \(G\) with maximum vertex degree \(\Delta\geq 8\). The authors prove the following main results. (1) For a planar graph \(G\), \(\chi(G^2)\leq \lceil{5\over 3}\Delta\rceil+ 78\). (2) For a planar graph \(G\), if \(\Delta\geq 241\), then \(\chi(G^2)\leq\lceil{5\over 3}\Delta\rceil+ 25\). They show how to transform the proof into a colouring algorithm which uses at most \(\lceil{5\over 3}\Delta\rceil+ 78\) colours. Since there are \(O(n)\) iterations of the main procedure, the total running time of the algorithm would be \(O(n^2)\).