论文部分内容阅读
本文研究简单平面图.图G是非正常(d1，d2,…,dk)-可染的，即(d1，d2，…，dk)-可染的，当且仅当:存在V(G)的一个剖分V(G)=V1∪V2∪…∪Vk，使得(∨)i∈[1，k],△(G[Vi])≤di.这一定义包含了正常k-染色(d1=d2=…=dk=0)和d-非正常k-染色（d1=d2=…=dk=d≥1）. 图的非正常染色是由Burr, Jacobson(1985)，Harary, Jones(1985)和Cowen，Cowen，Woodall(1986)分别提出的.(S)krekovski和Eaton，Hull在1999年分别提出了列表非正常染色的概念.由于3-染色剩下的问题越来越困难，很多学者把目光放在了非正常3-染色上，通过解决某些图的非正常3-染色再逐步逼近到3-染色.Steinberg(1976)曾提出著名的猜想:不含4-，5-圈的平面图是(0，0，0)-可染的.Zhang and Xu(2007)也提出过如下问题:不含相邻三角形的平面图是否是(3，1)*-可选的？ 本文主要围绕以上猜想和问题讨论平面图的非正常染色.第一章介绍了本论文所涉及的有关定义，并对非正常染色研究现状做了一个综述.第二章主要讨论不含某些特殊结构的平面图的(1，1，0)-染色并且改进了一些已有的非正常染色的结果.第三章主要研究不含某些特殊结构的平面图的(3，1)*-可选择性.