کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4649740 1342465 2009 13 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Entire choosability of near-outerplane graphs
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
Entire choosability of near-outerplane graphs
چکیده انگلیسی

It is proved that if GG is a plane embedding of a K4K4-minor-free graph with maximum degree ΔΔ, then GG is entirely 7-choosable if Δ≤4Δ≤4 and GG is entirely (Δ+2)(Δ+2)-choosable if Δ≥5Δ≥5; that is, if every vertex, edge and face of GG is given a list of max{7,Δ+2}max{7,Δ+2} colours, then every element can be given a colour from its list such that no two adjacent or incident elements are given the same colour. It is proved also that this result holds if GG is a plane embedding of a K2,3K2,3-minor-free graph or a (K2̄+(K1∪K2))-minor-free graph. As a special case this proves that the Entire Coluring Conjecture, that a plane graph is entirely (Δ+4)(Δ+4)-colourable, holds if GG is a plane embedding of a K4K4-minor-free graph, a K2,3K2,3-minor-free graph or a (K2̄+(K1∪K2))-minor-free graph.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 309, Issue 8, 28 April 2009, Pages 2153–2165
نویسندگان
,