Publication details
Extending partial 5-colorings and 6-colorings in planar graphs
| Authors | |
|---|---|
| Year of publication | 2006 |
| Type | Article in Periodical |
| Magazine / Source | JOURNAL OF COMBINATORIAL THEORY SERIES B |
| Citation | |
| Doi | http://dx.doi.org/10.1016/j.jctb.2005.06.006 |
| Keywords | extension of graph colorings; coloring of planar graphs |
| Description | 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 subset of 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 vertical bar X vertical bar + 5 vertical bar(X vertical bar) if k = 5 and 17 vertical bar X vertical bar - 48 if k = 6. (c) 2005 Elsevier Inc. All rights reserved. |