论文部分内容阅读
令图G=(V(G),E(G)).G的一个k-着色,是指一个映射ψ:V(G)→{1,2,…,k}使得对每一个i,1≤i≤k,G[Vi]是无边集,这里G[Vi]表示颜色为i的点的导出子图.称图G是k-可着色的如果它存在一个k-着色;G的一个(c1,c2,…ck)-着色,是指一个映射ψ:V(G)→{1,2,…,k}使得对每一个i,1≤i≤k,G[Vi]的最大度不超过ci.称图G是(c1,c2,…ck)-可着色的如果它存在一个(c1,c2,…ck)-着色. 近些年来,四色问题作为图论方向的一个经典问题被众多学者所研究.1977年,Appel和Haken在计算机的帮助下证明了该问题.为了寻找一种纯数学分析的方法来解决该问题,很多专家学者开始对可平面图的三色问题进行深入研究.2003年,Borodin和Raspaud猜想每一个不含相交三角形和5-圈的可平面图是3-可着色的.本文证明了每一个不含相交三角形和5-圈的可平面图是(2,0,0)-可着色的.