Article ID Journal Published Year Pages File Type
4657500 Journal of Combinatorial Theory, Series B 2006 11 Pages PDF
Abstract

Let D be a disc and let X be a finite set of points on the boundary of D. A set C of k-colorings of the points X is called k-feasible if there exists a plane graph G drawn in the disc D with X⊆V(G) such that precisely colorings contained in the set C can be extended to proper k-colorings of G. We show that for each k-feasible set C, there exists such a plane graph G of order at most |X|+5|X| if k=5 and 17|X|-48 if k=6.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics