全图的列表点荫度及平面图的列表着色

作     者：韩英 

作者单位：新疆大学 

学位级别：硕士

导师姓名：宝音都仍

授予年度：2009年

学科分类：07[理学] 070104[理学-应用数学] 0701[理学-数学] 

主      题：点荫度 列表点荫度 全图 平面图 列表着色 

摘      要：本论文首先研究了全图的列表点荫度,提出猜想:对任意图G,有[(Δ(G)+1)/2]≤ρ(T(G)) =ρ(T(G))≤[(Δ(G)+2)/2],其中T(G)是图G的全图.并证明了对任意二退化图,[(Δ(G)+1)/2]≤ρ(T (G))≤ρ(T (G))≤[(Δ(G)+2)/2]成立.特别地,如果图G是不同构于P的外可平面图,并且Δ(G)≠3,则可得到ρ(T(G)) =ρ(T(G)) =[(Δ(G)+1)/2]. 其次,文章研究了平面图的列表着色问题,给出了平面图3-可选的一个充分条件.图G = (V,E)称为L-可着色的,如果对给定的列表L = {L(v) : v∈V (G)},存在图G的一个正常着色c,满足c(v)∈L(v).如果对任何|L(v)|≥k的列表,图G都是L-可着色的,则称图G为k-可选的.本文我们证明了不含4-圈、5-圈和7-圈,并且三角形之间距离不小于2的平面图是3-可选的.