周 圆，陈光亭，陈 永，张 安

(1.杭州电子科技大学理学院，浙江 杭州 310018；2.台州学院电子与信息工程学院，浙江 台州 318000)

0 引 言

顶点着色图在多个学科领域有着十分重要的作用，文献[1]介绍了其在生物信息学中的应用。文献[2]给出了在一般图中找最大独立集问题是NP-hard。文献[3]提出限制奇偶度时的有界度图上的近似算法，对于一些特殊的图，文献[4-6]分别提出在无爪图(claw-free graph)、无P5路的图(P5-free graph)和完美图(perfect graph)中，寻找最大独立及问题(Maximum Independent Problem，MIP)是多项式时间内可解的，文献[7]提出，对于余图(cograph)和弦图(chordal graph)，可在线性时间内解出MIP问题。当前对颜色数最多的独立集问题(Maximum Colorful Independent Set Problem，MCISP)的研究中，文献[8]提出聚类图(cluster grpah)和树(tree)中的MCISP问题是多项式时间内可解并给出相关算法，而在无P5路(P5-free graph)图和余图(cogrpah)中，求解MCISP问题是NP-hard。

1 一般二部图上的MCISP问题

定义1给定任意图G=(V,E)，将图G中的顶点集V分为两部分，分别是V1和V2且V1和V2都是独立集，图G中的边集E由V1中的顶点到V2中的顶点的连线组成的图称为二部图[10],记作G=(V1,V2,E)。

定义2给定任意二部图G=(V1,V2,E)，V1中的每一个顶点与V2中的每一个顶点之间都有边的图称为完全二部图[10]，记作KV1,V2。

定义3给定任意二部图G=(V1,V2,E)和颜色集C，使得G中每个顶点都着有C中至少一种颜色的图为顶点着色图[8]，其中C中的颜色由自然数N表示，不同的自然数i表示不同的颜色，i∈N。|C(Vi)|表示不同集合的不同颜色数，i∈{1,2}，记作Gc=(V1,V2,E)。

对于任意给定的顶点着色二部图Gc=(V1,V2,E)，在图G上找到一个包含G中顶点颜色数最多的独立集S，其中集合S记作算法解得到的不同颜色顶点组成的集合，S*表示最优解中颜色不同的顶点组成的集合，这一问题叫做二部图上的MCISP问题。……