论文部分内容阅读
图G的一个正常k顶点染色是指一个映射φ:V→{1,…,k},使得对任意uv∈E(G),满足φ(u)≠φ(v).若图G有一个正常k点染色,那么就称图G是k点可染色的.
图G的一个顶点色列表L是一个颜色集合簇,它指定G的每个顶点u一个颜色集合L(u).若G有一个正常的顶点染色φ,使得对每一个顶点u∈V(G),有φ(u)∈L(u),则称G为L顶点可染的,或者称φ是G的一个L染色.若对每一个满足|L(u)|≥k,u∈V(G)的L,G都是L点可染的,则称G是k(点)可选择的.
1979年,P.Erdos等人刻画了2可选择图并提出猜想:每一个平面图都是5可选择的,且存在着非4可选择的平面图.1993年,Voigt成功地构造出了非4可选择的平面图.随后,Thomassen证明了每一个平面图都是5可选择的.由此,自然产生这样一个问题:哪些平面图是4可选择的,哪些平面图是3可选择的?1996年,Gutner证明了这个问题是NP困难的.因此,寻找平面图是3或4可选择的充分条件成为图的染色理论中的一个重要研究课题。
1976年,Steinberg猜想:不含4圈和5圈的平面图是3可染色的.Erdos建议去研究下述问题:是否存在一个整数七,使得没有4至尼圈的平面图是3可染色的.到目前为止,Erdos问题的最佳结论为:Borodin等人在1995年得到的k=7.但是离Steinberg猜想还有较大距离.
本文在前人的工作基础上,运用延拓性引理和Discharge、粘点收缩偶面等方法,继续研究平面图的3可染色和3可选择性问题,证明了:
(1)每一个不含4,6,7,9圈的平面图是3可选择的;
(2)每一个不含4,5,8,9圈的平面图是3可选择的;
(3)每一个不含4,7,9圈的平面图是3可染色的.