Extending partial 5-colorings and 6-colorings in planar graphs (Q2581502)

Let \(X\) be a finite set of points on a boundary of a disc \(D.\) A set \(C\) of \( k\)-colorings of \(X\) is called \(k\)-feasible if there exists a planer graph \(G\) drawn on \(D\) so that \(X\subset V(G)\) and only colorings from \(C\) can be extended to proper \(k\)-colorings of \(G.\) This notion has been introduced by \textit{M. DeVos} and \textit{P. Seymour} [J. Comb. Theory, Ser. B 88, 219--225 (2003; Zbl 1020.05027)]. In this paper it is proved that for each \(k\)-feasible set of colorings there is a planar graph \(G\) of order at most \(\left| X\right| +5^{| X|}\) for \( k=5,\) and of order at most \(17\left| X\right| -48\) for \(k=6.\)