论文部分内容阅读
染色问题一直是图论中的热点话题之一,且至今已有十分丰富的研究结果.1990年, Bodlaender在关于计算机科学中的图论专题讨论会上做了关于某些色策略的专题报告[1],基于图的正常顶点着色的概念,首先引入了图的对策着色的概念.所谓图的对策着色,如同两人(A和B)对弈,选手A试图给出图的正常顶点着色,而选手B则设法阻止该事件的发生.设图G=(V,E)是n阶有限的简单图,l是一个正的常数, X是t种颜色的集合,两个人在图G上对弈,选手A和B交替易手,最后完成对弈至多移动n步,每一步包括一名选手挑选一个尚未着色的顶点v,且从颜色集X中给它分配一个颜色a,使得a不同于已分配到v的邻点的颜色.若n步以后图G被正常着色,则选手A获胜:若在该图的全部顶点被着色之前达成僵局,即颜色集X中无色可用,则B获胜.图G的对策色数是使选手A获胜的最小的t,记为χ_g(G).为了简单起见,我们分别称上述对策着色和对策色数为色对策Ⅰ和对策色数Ⅰ.在色对策Ⅰ的基础上, Chen,Schelp和Shreve对选手B再附加条件,提出了一种新的对策着色,即图G的对策着色Ⅱ[2],这个条件是限制选手B只能利用选手A已引入的颜色之一,除非他为保证图着色是正常的而不得不利用X中的一种新颜色.图G对策色数Ⅱ是选手A在对策着色Ⅱ中有一个获胜策略的最小的t,记为χ_g~*(G).关于图的对策着色Ⅱ,目前得到的整体结果还不是很多.仅知Mycielski图、路、圈、轮图及轮扇图的对策色数Ⅱ.本文第二章,利用顶点标号的方法,对θ图和广义θ图及路的倍图对策着色情况进行讨论,并得出他们的对策色数Ⅱ.2002年,张忠辅等人提出图的邻点可区别边色数,并得到了圈、完全图等特殊图类的邻强边色数.本文给出了某些特殊图类的邻点可区别边色数.在第三章中,运用分析结构及归纳方法,得到了若干倍图的邻点可区别边色数以及它的界.在第四章中,用分析法得到了积图的邻点可区别边色数.主要结果如下:定理定理设C_n是n≥3的n阶圈，有定理