Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4657500 | Journal of Combinatorial Theory, Series B | 2006 | 11 Pages |
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