外平面图的列表着色

摘要

在大多数实际的点着色问题中，对某些确定的点所着颜色都有一些限制，因此，研究点的列表着色对解决实际问题有一些重要的意义。
　　 对于某个确定的图G，∣V(G)∣=n，且G为s列表可着色，即xl(G)=s.假设G的每个点只能着指定的t种颜色，t≤s，此时记λt，s为G中能被着色的点数的最大值，且每个点的列表长为t.Albertson，Grossman，and hass[1]中猜想λt，s≥tn/s.本文主要研究这样两个问题，首先，用概率的方法估算λt，s的范围.其次，讨论对于外平面图G，用数学归纳法证明λ2，3≥2/3n。