几种图的对策着色和对策色数.pdf

维普资讯
第��卷第�期�云南民族大学学报�自然科学版�����.�����.��
����年��月������������������������������������������������������������������������.�����
几种图的对策着色和对策色数�
江�燕�杨�帆�
�华中师范大学数学与统计学学院,湖北武汉��������
摘要介绍了一种新的色对策和对策色数,比较了�,运用�
顶点标号方法,给出获胜策略.�
关键词顶点着色;对策着色;对策色数�
【中图分类号】����.��【文献标识码】��【文章编号】����—�����������������—���
����������������������������������������������������������
�������������������
�����������������������������������,������������������������������,������������,�������
��������:��������������������������������������������������������������������������������������������
���������������������������������.�����������������������������,��������������������������������������������
�������������.�
���������:��������������;��������������;����������������������
点着色,则选手�获胜;若在该图的全部顶点被着�
�对策着色和对策色数�
色之前达到僵局,即对每一个尚未着色的顶点和��
本文讨论的图都是连通的、无向的、有限的简单�中每一种颜色�,�都与�个着色为�的顶点相邻,�
�������,������,�,△分�则��的对策色数,记为����,是使选手�
别表示图�的顶点集、边集和最大度,����表示图��有�个获胜策略的最小的�,即使选手�获胜,双�
的顶点�的度数.�是一个有限整数集,表示颜色�方所利用的颜色的最少数目,我们称上述对策着色�
集,它的基数记为������.设�∈����,Ⅳ���表示�和对策色数为色对策�和对策色数�.�
的开邻域集,����表示�的闭邻域集,即������在色对策�的基础上,����,������和�������
��.一般地,对正整数�,�����Ⅳ�������,其�对选手�再附加�个条件:限制选手�只能利用选�
中Ⅳ������∈������,�����.图�的一个正常�手�已引人的颜色之一,除非他为保证图着色是正�
顶点着色是从�到�的一个映射�:对任意�,�∈�常的而不得不利用�中的��的对策�
, 如果删∈�,则����≠����.�色数Ⅱ是选手�在色对策Ⅱ中有�个选手