论文部分内容阅读
一个图G=(V(G),E(G)),如果用至多k种颜色就可以对它的所有顶点进行染色。使得每个顶点至多和d个与它染同种颜色的顶点相邻,则称图G是(k,d)﹡-可染的.其中,它的任意一个满足上述条件的染色称为图G的一个(k,d)﹡一染色.并记图G的非正常色数Xd(G)=min{k|图G是(k,d)﹡-可染色的).
图G是一个平面图,若存在G的一个平面嵌入使得G的某一个面上含有G中的所有顶点,则称图G为外可平面图.平面图G的边把整个平面分割成若干个连通区域,这些区域的闭包称为平面图G的面:其中,外部的无限区域称为外部面.如果外可平面图G有一个平面嵌入,使得G除了外部面以外的所有面都是三角形,则称G为极大外可平面图.
对于外可平面图非正常染色问题,L.J.Cowen,R.H.Cowen和D.R.Woodall于1986年在文献[6]中证明了每个外可平面图都是(2,2)﹡-可染的,并给出了一个不能(2,1)﹡-可染的外可平面图.
本文从外可平面图的结构入手,详细讨论了无三角形外可平面图和只含三角形外可平面图(即极大外可平面图)的(2,1)﹡-可染性,得到结论:每个无三角形的外可平面图都是(2,1)﹡-可染的;并分别给出了无割点极大外可平面图和有割点极大外可平面图(2,1)﹡-可染的刻画.