You can't paint yourself into a corner (Q1272489)

Thomassen posed the following problem: Suppose \(G\) is a planar graph and \(W\subseteq V(G)\) such that the distance between any two vertices in \(W\) is at least 100. Can a 5-coloring of \(W\) be extended to a 5-coloring of \(G\)? It is known that no 4-coloring result of this nature can hold. In this paper a solution to Thomassen's problem is provided and it is proved that: (i) for any planar graph \(G\) and \(W\subseteq V(G)\) such that the distance between any two vertices in \(W\) is at least 4 (resp., 3), any 5 (resp., 6) coloring of \(W\) can be extended to a 5 (resp., 6) coloring of \(G\); (ii) for any graph \(G\) having \(\chi (G)=r\) and \(W\subseteq V(G)\) such that the distance between any two vertices in \(W\) is at least 4, any \((r+1)\)-coloring of \(W\) can be extended to an \((r+1)\)-coloring of \(G\); (iii) the previous conclusion also holds if \(W=W_{1}\cup W_{2}\cup \cdots \cup W_{m}\), where each \(W_{i}\) is a clique, \(| W_{i}| \leq k\) for every \(i\), and \(d(x,y)\geq 6k-2\) whenever \(x\in W_{i}\), \(y\in W_{j}\) and \(i\neq j\).