论文部分内容阅读
在大多数实际的点着色问题中,对某些确定的点所着颜色都有一些限制,因此,研究点的列表着色对解决实际问题有一些重要的意义。
对于某个确定的图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。