کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4657500 1343742 2006 11 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Extending partial 5-colorings and 6-colorings in planar graphs
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
Extending partial 5-colorings and 6-colorings in planar graphs
چکیده انگلیسی

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.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Combinatorial Theory, Series B - Volume 96, Issue 1, January 2006, Pages 100-110