Publication details

Extending partial 5-colorings and 6-colorings in planar graphs

Authors

KRÁĽ Daniel

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.

You are running an old browser version. We recommend updating your browser to its latest version.

More info