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