若干图类的关联着色与关联对策着色的研究

摘要

本文从图的结构性质出发，利用归纳法和反证法研究了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。

目录

封面

声明

中文摘要

英文摘要

目录

Contents

1 引 言

2 Johnson图与广义Petersen图的关联色数

2.1基本概念与预备引理

2.2 Johnson图的关联色数

2.3 广义Petersen图的关联色数

3 圈关联对策着色的研究

3.1基本概念与预备引理

3.2主要结果及其证明

4 结 束 语

致谢

参考文献

硕士期间研究成果