摘要
一个图的竞赛色数是由Bodlaender[1]首次提出的.最近,周,王,朱在文献[2]中提出了松弛竞赛色数的概念,此概念在图论中占有很重要的地位.它把对策论和染色问题紧密联系在一起.一个图的松弛竞赛色数是通过两个人的竞赛来定义的.设G=(V,E)是一个图,k 和d都是正整数,则(k,d)-松弛竞赛染色是指两个人,比如Alice和Bob,交替的使用颜色集X中k种颜色对G中顶点染色,并且Alice先走,我们说X中的一个颜色α对顶点υ是合法的,是指由所有染颜色α的顶点导出的子图的最大度至多是d,其中Alice和Bob每走一步都是用合法颜色染未染色点.如果图G的所有顶点都被合法染色,则Alice赢;否则,Bob赢.Alice的目的是生成一个策略使得她在游戏结束时能赢,而Bob的目的是想法阻止Alice赢.定义d为缺陷度,则图G的d-松弛竞赛染色数X<,g><'d>(G)是指Alice在上述染色游戏中获胜所用的最小染色数.如今,关于树,外平面图及偏k-树的松弛竞赛染色已引起众多学者的研究,该文主要研究森林的松弛竞赛色数.
NETL