论文部分内容阅读
设κ为正整数，G为图．作者给G每点一个长为κ的任意表，如果存在一个点着色，使得每个点都可从表中得到一种颜色，则称G为k-可选色的．本文中证明了一些不含相邻三角形的平面图是4-可选色的．
(1)不含相邻三角形，并且四面和三面不相邻的平面图是4-可选色的．
(2)不含相邻三角形，并且四面的距离至少为3的平面图是4-可选色的．
由于直接证明(1)(2)有困难，本文中给出了两个重要引理，由这两个引理完成了本文的证明．
(3)不含相邻三角形，四面和三面不相邻，并且δ≥4的平面图至少含有满足下列条件之一的圈或子图：
(i)每点都为4度点的4-圈．
(ii)每点都为4度点，并且恰含有一弦υ<,1>υ<,3>的6-圈υ<,1>υ<,2>…υ<,6>υ<,1>
(iii)子图．
(4)不含相邻三角形，四面的距离至少为3，并且δ≥4的平面图至少含有满足下列条件之一的圈或子图：
(i)每点都为4度点的4-圈．
(ii)每点都为4度点，并且恰含有一弦u<,1>u<,3>的6-圈u<,1>u<,2>…u<,6>u<,1>
(iii)子图．
(iv)u<,1>为5度点，其余都为4度点并恰含有一弦u<,1>u<,3>的圈u<,1>u<,2>…u<,k>u<,1>(k≥5)．
(v)u<,2>和u<,k>为5度点，其余都为4度点并恰含有两弦u<,2>u<,2>和u<,5>u<,k>的圈u<,1>u<,2>…<,5>u<,1>u<,2>u<,3>…u<,k>u<,1>(k≥4)．