论文部分内容阅读
1979年,P. Erdios等人刻画了2可选择图并提出猜想:每一个平面图都是5可选择的,且存在着不是4可选择的平面图。1993年,Voigt成功地构造出了不是4可选择的平面图。随后,Thomassen证明了每一个平面图都是5可选择的。由此,自然产生这样一个问题:哪些平面图是4可选择的,哪些平面图是3可选择的?1996年,Gutner证明了这个问题是NP困难的。最近,Mickaёl Montassier提出:哪些条件能保证每个平面图都是3可选择的?因此,寻找平面图是3或4可选择的充分条件成为图的染色理论中的一个重要研究课题。本文关注平面图的3可选择性。
本文在前人的工作基础上继续研究平面图的3可选择性问题,证明了:
(1)每一个不含4,5,9圈且任意两个三角形距离至少为3的平面图是3可选择的。
(2)每一个不含4,6,8,9圈的平面图是3可选择的。
(3)每一个不含4,7,8,9圈的平面图是3可选择的。