邵泽玲[1]2003年在《外平面图的松弛竞赛色数》文中研究表明一个图的松弛竞赛色数是由周，王，朱在[21]中提出的，并且它在图论中是极其有意义的。它把对策论和染色问题紧密联系在一起。近年来，人们对该领域进行了大量的研究和探索，取得了不少成果，同时仍存在许多未解决的问题，本文首先系统地总结了松弛竞赛色数的研究成果和研究进展。其次通过给Alice跳的步骤和染色规则，证明了，如果G是一个外平面图，缺陷度d=2，3，4，k=7-d，那么对于在G上进行的(k，d)-松弛染色竞赛，Alice能赢，即x_g~d(G)≤k。此结论扩充了[22]中的结论。此外本文还讨论了在外平面图G上进行的(6，1)-松弛染色竞赛和(2，5)-松弛染色竞赛两种情况。
何文杰, 马俊霞, 邵泽玲, 许燕, 米洪海[2]2002年在《外平面图的松弛竞赛色数》文中认为主要研究外平面图的松驰竞赛色数。如果缺陷度d =2 ,3 ,4 ,k =7-d ,我们能够分别给Alice一个策略 ,使得对 (k ,d) 松弛染色竞赛Alice能赢。
许燕[3]2003年在《森林的松弛竞赛色数》文中研究表明一个图的竞赛色数是由Bodlaender[1]首次提出的。最近，周，王，朱在文献[2]中提出了松弛竞赛色数的概念，此概念在图论中占有很重要的地位。它把对策论和染色问题紧密联系在一起。一个图的松弛竞赛色数是通过两个人的竞赛来定义的。设G=(v，E)是一个图，k和d都是正整数，则(k，d)-松弛竞赛染色是指两个人，比如Alice和Bob，交替的使用颜色集X中k种颜色对G中顶点染色，并且Alice先走，我们说X中的一个颜色。对顶点v是合法的，是指由所有染颜色。的顶点导出的子图的最大度至多是d，其中Alice和Bob每走一步都是用合法颜色染未染色点。如果图G的所有顶点都被合法染色，则Alice赢；否则，Bob赢。Alice的目的是生成一个策略使得她在游戏结束时能赢，而Bob的目的是想法阻止Alice赢。定义d为缺陷度，则图G的d-松弛竞赛染色数X_g~d(G)是指Alice在上述染色游戏中获胜所用的最小染色数。 如今，关于树，外平面图及偏k-树的松弛竞赛染色已引起众多学者的研究，本文主要研究森林的松弛竞赛色数。我们用一个分离策略证明了对任意的树G，当松弛量d=2时，它的松弛竞赛色数X_g~d(G)=2。这个结果回答了Dunn和Kierstead在[3]中提出的问题。
马俊霞[4]2003年在《一个新的激活策略在偏K—树上的应用》文中指出本文主要研究的是偏k-树在松弛度为d的情况下的松弛竞赛色数问题。图的松弛竞赛色数首先是由周，王，朱[1]提出来的，它把对策论和染色理论两个重要问题紧密联系在一起，从而使它在图染色理论中占有很重要的位置，并引起了众多专家人士的兴趣和关注。关于图的松弛竞赛色数的定义我们将在正文定义3．1．3中给出。对树，外平面图，偏k-树及伪偏k-树的松弛竞赛染色已在不同程度上得到了一些研究，并取得了一些相应的结果。本文正是在已有研究的基础上，对偏k-树的松弛竞赛色数进行了进一步的研究，使得在松弛度d不小于2k+1的情况下，对这个(r，d)-松弛竞赛染色，有，它是文章[2]中结果的一个很好的改进。
高辉[5]2006年在《图的对策着色问题研究》文中研究指明图的着色理论是图论的重要分支之一,是图论研究中的最活跃的课题之一.特别是图的对策色数的研究是一个引人注目的课题,它在网络设计和计算机科学中有着广泛的应用.目前,关于图的对策色数已有很多结论.现在广泛研究的问题有:图的点对策着色,图的边对策着色,图的松弛对策着色问题等.首先全面分析了图的点对策着色问题,对某些定理的下界,给出了具体的例子.对树边对策着色中的分裂策略这一重要的研究思想,进行了重点介绍和研究.我们还提出了第二边对策色数这个概念,在此基础上给出了几类简单图的第二边对策色数的上界.主要的工作是对一些特殊图类的边对策色数进行了研究,给出了类圈图,扇图,花形图和Halin图的边对策色数的上界,并且证明了关于类圈图和Halin图的结果是紧的,这就给平面图,外平面图的研究提供了很好的例子.最后对于松弛对策着色问题进行了初步的探讨,提出了边松弛对策着色问题,给出了边松弛对策色数的概念,并给出了链、圈的边松弛对策色数的上界.
杜建伟[6]2006年在《1-树图的邻点可区别全染色》文中指出在文献[2]中张忠辅等提出了图的邻点可区别全染色的概念,即:设G是阶至少为2的连通简单图,k是正整数,f是V(G)∪E(G)到{1,2,…,k}的映射。对任意u∈V(G),记C(u)={f(u)}∪{f(uv)|uv∈E(G),u∈V(G)}。如果 (ⅰ)对任意:uv,uw∈E(G),u≠w,有f(uv)≠f(vw); (ⅱ)对任意uv∈E(G),有f(u)≠f(v),f(u)≠f(uv),f(v)≠f(uv),则称f为G的k-正常全染色。进一步,如果f还满足 (ⅲ)对任意uv∈E(G),有C(u)≠C(v),则称f为G的k-邻点可区别全染色(简记为k-AVDTC)。称min{k|G有k-邻点可区别全染色}为G的邻点可区别全色数,记作x_(at)(G)。其中C(u)称为点u在f下的色集合。本文研究了1-树图的邻点可区别全染色,并给出了1-树图的邻点可区别全色数。 在本文第一章我们分别就本文所用的术语、记号和结论作出了总结。在第二章研究了单圈图的邻点可区别全染色,并给出其邻点可区别全色数。在第叁章中,我们讨论了1-树图的邻点可区别全染色。在3.1节中给出了Δ(G)≤3的1-树图的邻点可区别全色数.用另一个归纳基础,在3.2节中给出了Δ(G)≥4的1-树图的邻点可区别全色数。主要结果如下:定理 对单圈图G有:其中V_Δ={u|u∈V(G),d(u)=Δ(G)}。定理 对1-树图G有:其中V_Δ={u|u∈V(G),d(u)=Δ(G)}。
董桂香, 尤海燕, 许广镇[7]2010年在《几类笛卡尔积图的关联色数研究》文中研究指明图的关联着色问题是图着色理论的重要组成部分之一,确定图的关联色数是一个具有重要的实际价值和理论意义的课题,关于图的关联着色还没有十分深刻的结果,研究了路与完全二部图的笛卡尔积图的关联着色、圈与完全二部图的笛卡尔积图的关联着色、完全图与完全二部图的笛卡尔积图的关联着色,根据笛卡尔积图的特点,采用穷染的方法确定了其中部分图类的关联色数,从而验证了关联着色猜想在这些笛卡尔积图类中是正确的。
参考文献：
[1]. 外平面图的松弛竞赛色数[D]. 邵泽玲. 河北工业大学. 2003
[2]. 外平面图的松弛竞赛色数[J]. 何文杰, 马俊霞, 邵泽玲, 许燕, 米洪海. 河北省科学院学报. 2002
[3]. 森林的松弛竞赛色数[D]. 许燕. 河北工业大学. 2003
[4]. 一个新的激活策略在偏K—树上的应用[D]. 马俊霞. 河北工业大学. 2003
[5]. 图的对策着色问题研究[D]. 高辉. 国防科学技术大学. 2006
[6]. 1-树图的邻点可区别全染色[D]. 杜建伟. 山西大学. 2006
[7]. 几类笛卡尔积图的关联色数研究[J]. 董桂香, 尤海燕, 许广镇. 山东建筑大学学报. 2010