学位论文 > 优秀研究生学位论文题录展示

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

作　者: 刘大琨
导　师: 王淑栋
学　校: 山东科技大学
专　业: 应用数学
关键词: 关联色数关联对策色数 Johnson图广义Petersen图
分类号: O157.5
类　型: 硕士论文
年　份: 2009年
下　载: 17次
引　用: 1次
阅　读: 论文下载

内容摘要

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

全文目录

摘要  5-6
ABSTRACT  6-9
1 引言  9-12
2 Johnson图与广义Petersen图的关联色数  12-25
  2.1 基本概念与预备引理  12-15
  2.2 Johnson图的关联色数  15-21
  2.3 广义Petersen图的关联色数  21-25
3 圈关联对策着色的研究  25-31
  3.1 基本概念与预备引理  25-26
  3.2 主要结果及其证明  26-31
4 结束语  31-32
致谢  32-33
参考文献  33-37
硕士期间研究成果  37

相似论文

关于几类图的邻点可区别关联色数的研究,O157.5
广义Petersen图P（N，3）的1-因子数的下界,O157.5
伪Halin图的着色,O157.5
图的BBC染色,O157.5
广义Petersen图的条件着色和L（2，1）-标号,O157.5
一类广义Petersen图P（N，k）的1-因子数及相关问题研究,O157.5
三正则图的条件着色,O157.5
图的L（d，1）-标号,O157.5
若干图类的星边染色,O157.5
广义Petersen图的（a，d）-反边幻标号和图P_2□P_n的广播标号,O157.5
关于图的关联色数,O157.5
关于若干图类的着色问题,O157.5
图的关联着色与邻点可区别关联着色,O157.5
Johnson图的连通度、割集和哈密尔顿圈,O157.5
广义对称图,O152.7
循环图和广义Petersen图的支配参数,O157.5
若干图的（d，1）全标号和（2，1）标号的研究,O157.5
若干图的等全着色及彩虹支配问题的研究,O157.5
广义Petersen图和循环图的罗马支配研究,O157.5
若干类图支配问题的研究,O157.5