کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4649740 | 1342465 | 2009 | 13 صفحه PDF | دانلود رایگان |
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.
Journal: Discrete Mathematics - Volume 309, Issue 8, 28 April 2009, Pages 2153–2165