论文部分内容阅读
令G是一个有限简单无向图.对于图G,分别用V(G),E(G)和Δ(G)表示它的顶点集、边集及最大度.图G的一个k-染色是指将G的顶点集划分为k个集合V1,V2,...,Vk,使得每个Vi中的元素均染颜色i.若每个导出子图G[Vi]均是一个独立集,则G有一个正常的k-染色;若导出子图G[Vi]的最大度为d,则G有一个d-非正常k-染色.此概念于1986年由Cowen等人首次提出并研究.若G有一个d-非正常k-染色,则称G是d-非正常k-可染的,简称(k,d)*-可染.显然,(k,0)*-染色等同于正常的k-染色.令i和j是两种不同的颜色.若圈C上的顶点交替染i色和j色,则称C是2-色交替圈.若图G是(k,d)*-可染的且无2-色交替圈,则称G是无圈(k,d)*-可染的.Erdos和Vizing在20世纪70年代独立提出了列表染色的概念.它与频道设计和资源分配的问题密切相关,与染色概念既相互联系又有着明显的区别.图G的一个顶点色列表配置L是一个颜色集合簇,它指定G中的每个顶点v一个颜色列表L(v).1999年,Eaton等人在非正常染色的基础上,给出了非正常列表染色的相关定义.图G的一个(L,d)*-染色指的是存在一个映射π,使得对于每个v∈ V(G),满足π(v)∈L(v)且v至多有d个邻点与它同色.如果对每个满足|L(v)| ≥ k的色列表配置L,G都有一个(L,d)*-染色,那么称G是(k,d)*-可选的.类似地,G是(k,0)*-可选的等价于G是k-可选的.2007年,Esperet等人研究了图的无圈非正常列表染色.若存在一个映射π,使得对于每个v∈ V(G),满足v至多有d个邻点与它同色且不含2-色交替圈,则称G有一个无圈d-非正常染色π.若对任意的顶点色列表配置L={L(v)|v∈V(G)},图G都有一个无圈d-非正常染色π使得对每个顶点v∈ V(G)有π(v)∈ L(v),则G被称为无圈d-非正常L-可染的.类似地,若对每一个满足|L(v)| ≥k的色列表配置L,G是无圈d-非正常L-可染,则称G是无圈d-非正常k-可选的,简称无圈(k,d)*-可选的.本文,我们着重研究图的无圈(k,d)*-可选性.在第一章中,先介绍与本文相关的基本概念和一些术语,再对该领域的已有研究成果做一个简单的概述,最后罗列出本文的主要结果.在第二,第三以及第四章中,我们均使用反证法,通过构造极小反例,对可约构形加以深入分析,结合代数方法、色延拓等技巧证明了以下三个结果:(1)最大度为4的图(除K4,4)是无圈(3,3)*-可选的.(2)最大度为4的图是无圈(5,1)*-可选的.(3)最大度为5的非5-正则图是无圈(4,4)*-可选的.需指出,结果(1)和结果(3)都是最优的.另外,Fiedorowicz和Sidorowicz证明了最大度为4的图是无圈(3,3)*-可染的.该结果已发表在《中国科学:数学》(英文版)期刊上.因此,结果(1)是对以上结论的一个改进.