List-colouring the square of a \(K_4\)-minor-free graph (Q941324)

The square \(G^2\) of a graph \(G\) has the same vertex set as \(G\), and two vertices are adjacent in \(G^2\) if they are within distance two of each other in \(G\). The list chromatic number of \(G\) is denoted by \(\text{ch}(G)\). The degeneracy of \(G\) is the smallest integer \(k\) such that every subgraph of \(G\) contains a vertex with degree at most \(k\) and denoted degeneracy\((G)\). The following is proved in this paper. Let \(G\) be a \(K_4\)-minor-free graph with maximum degree \(\Delta\). Then \[ \text{ch}(G^2) \leq \begin{cases} \Delta + 3 &\text{if }\Delta=2\text{ or }3; \\ \left\lfloor \frac{3}{2} \Delta \right\rfloor + 1&\text{if }\Delta \geq 4,\end{cases} \] and we also have \[ \text{degeneracy}(G^2) \leq \begin{cases} \Delta + 2 &\text{if }\Delta= 2\text{ or }3; \\ \left\lceil \frac{3}{2} \Delta \right\rceil &\text{if }\Delta \geq 4.\end{cases} \]