\(2\)-distance coloring of planar graphs with maximum degree \(5\) (Q2075520)

A 2-distance colouring of a graph is an assignment of colours to the vertices such that vertices at distance 1 or 2 from each other have different colours. The 2-distance colouring number \(\chi_{2}(G)\) is the smallest \(k\) such that there is a 2-distance colouring with \(k\) colours. So for example every \(n\)-vertex graph \(G\) of diameter 2 has \(\chi_{2}(G)=n\). Note that \(\chi_{2}(G)\geq \chi(G)\) where \(\chi\) is the usual chromatic number. The paper under review considers proper 2-distance colourings of planar graphs of maximum degree 5. The main result being that such graphs have 2-distance colouring number at most 19. This is related to an influential, and still unsolved for some small values of \(\Delta\) the maximum degree, conjecture of \textit{G. Wegner} [Graphs with given diameter and a coloring problem. Techn. Rep., University of Dortmund (1977)] bounding above the 2-distance colouring number of a planar graph of maximum degree \(\Delta\) in terms of \(\Delta\). The previous best upper bound was 20. The proof uses configurations. A putative counterexample \(G\) with \(\vert V(G)\vert +\vert E(G)\vert\) as small as possible is taken. A number of reducible configurations are given and discharging is used, along with Euler's formula, to derive a contradiction. The authors speculate that it may be possible to reduce the upper bound 19 to 10.