外可平面图的(2,1)<'*>-染色问题

来源 :南京师范大学 | 被引量 : 0次 | 上传用户:shengaogao3
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
一个图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)﹡-可染的刻画.
其他文献
摘要:建筑业的资源、能源消耗巨大,在所在产业中名列第一。因此如何实现建筑业的减耗节能,成为国民经济持续、健康发展和建设节约性社会的重中之重。建筑信息模型(BIM)、绿色施工技术应用对建设工程管理的前沿理论、职业道德、新的法律法规、建筑技术发展趋势有了新的认识。其中我体会最深的是建筑信息模型 (BIM )和绿色施工技术 ,就谈谈对这两方面的认识和想法。    关键词 :BIM 绿色施工    中图分
期刊
摘要:SBS改性沥青具有很好的耐高温、抗低温能力;较好的抗车辙能力,在国内高等级公路、城市干道和机场跑道等的广泛应用,本文从施工工艺角度对此进行了分析。关键词:施工工艺施工质量系统工程  中图分类号:U416.217文献标识码: A 文章编号:   一.SBS改性沥青混合料的运输 1 根据拌和摊铺机生产能力以及运距计算车辆数,保证摊铺机摊铺时前面常保存有4~5辆待卸车,运输车辆采用大吨位运输车,保
期刊
本文研究的是成分数据在中国的一类经济结构中的应用。成分数据在经济中的应用越来越广泛,可以被用来表示产业结构、居民消费结构等。然而,成分数据有定和限制,并且不服从正态分