Extending partial colorings of graphs (Q1567669)

For a graph \(G\) let \(N[W]=\{v\in V(G)\mid v\) is adjacent to some vertex in \(W\}\cup W\), \(N^{0}[W]=W\) and \(N^{s+1}[W]=N[N^{s}[W]]\). Let \(\text{Pre}(r,d,t)\), resp. \(\text{PPre}(r,d,t)\) be the least \(k\) such that if \(G\) is an \(r\)-colorable graph, resp. perfect graph, \(W=W_{1}\cup W_{2}\cup \ldots \cup W_{n}\subset V(G)\) where \(\text{dist}(W_{i},W_{j})\geq d\) whenever \(i\neq j\), and \(f\) is a \(k\)-coloring of \(W\) such that \(f|W_{i}\) can be extended to an \(r\)-coloring of \(N^{t}[W_{i}]\) for all \(i\), then \(f\) can be extended to a \(k\)-coloring of \(G\). The purpose of this paper is to show how old techniques for coloring highly recursive graphs can be used to prove theorems concerning the extension of a partial coloring of a graph to a total coloring. It is proved that \(\text{Pre}(r,3,0)= r^{2}+r\), \(\text{Pre}(r,d,0)= 2r\) for all \(d\geq 4\), \(\text{Pre}(r,3,1)= r^{2}\), and \(\text{Pre}(r,d,1)\leq 2r\) for all \(d\geq 4\). By extracting a proof from \textit{J. H. Schmerl}'s paper [Can. J. Math. 32, 821-831 (1980; Zbl 0394.05021)] on coloring highly recursive graphs it is shown that \(\text{Pre}(r,d,1)= 2r-1\) for all \(d\geq 6\) and \(\text{Pre}(r,d,2)= 2r-1\) for all \(d\geq 5\). When \(G\) is a perfect graph by using a proof from the author's paper [Can. J. Math. 33, 1279-1290 (1981; Zbl 0458.05034)] it is proved that \(\text{PPre}(r,4r,2r-1)= r+1\).