| 【中文题名】 | 森林的松弛竞赛色数 |
| 【英文题名】 | The Relaxed Game Chromatic Number of Trees |
| 【学科专业】 | 应用数学 |
| 【论文级别】 | 硕士论文 |
| 【投稿时间】 | 2003-7-9 |
| 【中关键词】 | 色数,竞赛色数,松弛竞赛色数,树,森林, |
| 【英关键词】 | chromatic number,game chromatic number,relaxed game chromatic number,tree,forest, |
| 【分类导航】 | 数理科学和化学>数学>代数、数论、组合理论>组合数学（组合学）>图论> |
| 【论文摘要】 |
一个图的竞赛色数是由Bodlaender[1]首次提出的。最近，周，王，朱在文献[2]中提出了松弛竞赛色数的概念，此概念在图论中占有很重要的地位。它把对策论和染色问题紧密联系在一起。一个图的松弛竞赛色数是通过两个人的竞赛来定义的。设G=(v，E)是一个图，k和d都是正整数，则(k，d)-松弛竞赛染色是指两个人，比如Alice和Bob，交替的使用颜色集X中k种颜色对G中顶点染色，并且Alice先走，我们说X中的一个颜色。对顶点v是合法的，是指由所有染颜色。的顶点导出的子图的最大度至多是d，其中Alice和Bob每走一步都是用合法颜色染未染色点。如果图G的所有顶点都被合法染色，则Alice赢；否则，Bob赢。Alice的目的是生成一个策略使得她在游戏结束时能赢，而Bob的目的是想法阻止Alice赢。定义d为缺陷度，则图G的d-松弛竞赛染色数X_g~d(G)是指Alice在上述染色游戏中获胜所用的最小染色数。
如今，关于树，外平面图及偏k-树的松弛竞赛染色已引起众多学者的研究，本文主要研究森林的松弛竞赛色数。我们用一个分离策略证明了对任意的树G，当松弛量d=2时，它的松弛竞赛色数X_g~d(G... |
| 【论文题纲】 |
|
第一章 绪论 |
7-10 |
|
§1-1 图论的发展 |
7 |
|
§1-2 图的染色问题 |
7-8 |
|
§1-3 图的松弛竞赛染色的提出 |
8-10 |
|
第二章 图的基本知识 |
10-16 |
|
§2-1 图与子图 |
10-12 |
|
§2-2 顶点着色 色数 平面图 |
12-14 |
|
§2-3 外平面图及其它类型图 |
14-16 |
|
第三章 对于图染色的进一步研究 |
16-22 |
|
§3-1 图的竞赛染色的基本概念及主要结果 |
16-19 |
|
§3-2 松弛竞赛染色的基本概念及主要研究结果 |
19-22 |
|
第四章 森林的松弛竞赛色数 |
22-28 |
|
§4-1 一些定义及符号 |
22-23 |
|
§4-2 Alice的分离策略及染色规则 |
23 |
|
§4-3 关于森林F的松弛竞赛色数的一些引理和证明 |
23-27 |
|
§4-4 讨论 |
27-28 |
|
第五章 主要结论 |
28-29 |
|
参考文献 |
29-31 |
|
致谢 |
31 |
|
| 【DOI】 | LunWen.ID:2.2008.11423 |
