Extending partial 3-colourings in a planar graph
Let \(D\) be a disc, and let \(X\) be a finite subset of points on the boundary of \(D\). An essential part of the proof of the four color theorem is the fact that many sets of 4-colorings of \(X\) do not arise from the proper 4-colorings of any graph drawn in \(D\). In contrast to this, in this paper it is shown that every set of 3-colorings of \(X\) arises from the proper 3-colorings of some graph \(G\) drawn in \(D\). In other words, for every subset \(Q\) of 3-colorings of \(X\), there exists a drawing \(G\) in \(D\) with \(X\subseteq V(G)\), such that the subset of 3-colorings of \(X\) that can be extended to a 3-coloring of \(G\) coincides with \(Q\).
scientific article; zbMATH DE number 1965028