论文部分内容阅读
混合超图染色是图与超图染色的对偶与推广.但混合超图染色与传统超图染色有很多不同的性质,如混合超图的色可行集可能存在间隙(gap),这是混合超图与传统超图染色的本质区别,对混合超图染色理论及其应用研究非常重要.故一个重要的研究方向就是研究以任意给定的有限正整数集合S为色可行集的极小混合超图,即研究S的极小实现.其中,S的极小实现包括点极小实现和边极小实现. 本文在前人的研究基础上,从3-匀齐bi-超图的1-实现的极值问题出发,在已经构造的点数最小的3-匀齐bi-超图的基础上,运用放大色谱对应分量的维数或去掉约束色谱相应分量的某些边的方法,重新构造超图并讨论了3-匀齐bi-超图的点极小实现问题.这是本文的第一个研究重点. 因为混合超图的上色数是由C-超图确定,所以我们在已有的关于具有最小上色数为2的C-超图的最小边数的函数f(n,3)的基础上,给出了bi-超图的相关结论.这是本文研究的第二个重点.以下是本文的主要结构: 第一章首先提出了混合超图染色问题,然后进一步阐述了该问题的应用、基本知识以及丰富的理论内容,在这一章的最后介绍了本文的主要工作框架. 第二章给出了关于混合超图的色可行集的一些基本的定义、定理和性质,及在近几十年里对色可行集的实现的极值问题的研究所取得的主要成果和研究现状. 第三章介绍了本文的主要工作和得到的主要结论,给出3-匀齐bi-超图H的极小实现的两个结论(公式略). 第四章主要给出了混合超图染色理论的推广形式,并提出了一些可继续讨论的研究方向.