论文部分内容阅读
本文从图的结构性质出发，利用归纳法和反证法研究了Johnson图以及若干广义Petersen图的关联着色，得到：Johnson图的关联色数xi(J(t,M))=m(t-m+1)；当n≡0(mod4)，k为奇数时，广义Petersen图P(n,k)的关联色数xi(P(n,k))=4；当k=2,4时，广义Petersen图P(n,k)的关联色数xi(P(n,k))=5。 设G是一个有限图，两个人Alice和Bob轮流对图G的关联进行着色，使得相邻的关联着色不同。Alice首先开始着色，若无法再进行下去时着色结束。若着色结束后图G的每个关联都正常着色，则Alice获胜，否则Bob获胜。Alice获胜所用的最少颜色数称为图的关联对策色数，记为ιg(G)。 本文将圈的关联对策着色转化为关联图的对策着色，得到了n阶圈的关联对策色数ιg(Cn)=5。