论文部分内容阅读
本文考虑的图均为有限、简单、无向图。对于任意一个图G，它的顶点集、边集、面集、最小度和最大度分别用V（G）、E（G）、F（G）、δ（G）和△（G）来表示．
图G的一个正常全k—染色是从V（G）∪E（G）到颜色集{1，2，3…k}的一个映射λ，它使得任意相邻接或关联的元素x，y∈V（G）∪E（G），都有λ（x）≠λ（y）．如果图G有一个正常全k—染色，则称图G足全k—可染色的，定义XT（G）=min{k|G是全k—可染色的}为图G的全色数。显然，对任意图G，都有XT（G）≥△（G）+1．Behzad和Vizing在1965年分别独立提出了下面猜想：
全染色猜想（TCC）：任意图G，都满足χT（G）≤△（G）+2．
对于一般的图，人们已经证明当△（G）≤5时，TCC猜想成立．对于平面图，已经证明当△（G）≥7时，TCC猜想成立．从而全染色猜想对平面图只剩△（G）=6的情形尚未证明。对任意图G，如果XT（G）=△（G）+1，则称G是第Ⅰ类图；如果XT（G）=△（G）+2，则称G是第Ⅱ类图．目前，已经证明如果图G是△（G）≥9的平面图，则G是第Ⅰ类图．
本文中我们主要研究不含相邻短圈的平面图的全染色问题，其中的短圈是指长度小于等于5的圈．我们通过对顶点和面上的值进行重新分配，运用欧拉公式证明了若G是△（G）=6的平面图，且G中不含相邻的短圈，则XT（G）≥8；若G是△（G）=8的平面图，且G中不含相邻的短圈，则G是第Ⅰ类图．