论文部分内容阅读
图的着色问题在图论中占有重要地位.着色问题实质上就是划分问题,一种色对应于划分的一个部分.在经典着色问题中,我们将图的顶点(边)着色要求相邻的顶点(边)着不同的颜色.该文研究了一些广义着色问题,由以下四部分组成:1.导出匹配划分数.2.点荫度.3.准偶划分.4.相邻强边着色数.导出匹配划分数 该文对小直径图研究了该问题的计算复杂性,对一些特殊的图类给出了其导出匹配划分数的精确结果.点荫度不含圈的图称为一个森林或者一个无圈图.图G有导出森林k-划分是指V(G)存在划分(V<,1>,V<,2>,…,V<,k>)使得每个导出子图G[V<,i>]是一个森林.图G的点荫度[10,11,12]是指图G有导出森林k-划分的最小整数k,记为a(G).Garey和Johnson[16]证明了k≥3时图的导出森林k-划分问题是NP-完全的.吴永旗等人[42]证明了最大度为5的图的导出森林2-划分问题是NP-完全的,而最大度为4的图的导出森林2-划分问题是多项式时间可解的.Chartrand等人[11]证明了对所有的平面图G有a(G)≤3,并且指出这个界是紧的.关于点荫度的研究结果很多,主要是围绕点荫度的上界,特殊图,临界图以及它和其它参数的关系等方面展开的.准偶划分给定图G,如果V(G)可以划分成两个子集V1和V<,2>,使得V<,1>是一个独立集,V<,2>是一个无圈集,则称G是一个准偶图;这样的划分(V<,1>,V<,2>)称为G的一个准偶划分.该文提出了准偶图的概念,是基于以下四个方面的原因.Monien[3]指出,Garey等人[17]的证明中蕴含着判定给定的图G是否存在一个独立集S使得G-S是一个森林是NP-完全的,也就是说,一般的准偶图的判定问题是NP-完全的.Brandstadt等人[3]证明了判定给定的最大度为4的偶图G是否存在一个独立集S使得G-S是一个树是NP-完全的,但是这个结果不能蕴含最大度为4的准偶图的判定问题的NP-完全性.该文研究了准偶图判定问题的计算复杂性.相邻强边着色数