| 【中文题名】 | 几类特殊平面图上的二人对策着色 |
| 【英文题名】 | Game Coloring of Some Particular Planar Graphs |
| 【学科专业】 | 运筹学与控制论 |
| 【论文级别】 | 硕士论文 |
| 【投稿时间】 | 2004-10-19 |
| 【中关键词】 | 对策着色,放松对策着色,可行色,放松对策色数,二叉树,树 |
| 【英关键词】 | game coloring,relaxed game coloring,feasible color,relaxed game chromatic number,binary tree,tree,outerplanar graph,triangulation,imitative dual graph,minimum dominating set,wheel,fan, |
| 【分类导航】 | 数理科学和化学>数学>运筹学>对策论（博弈论）>> |
| 【论文摘要】 | 这篇文章讨论在图上的二人对策着色：设t，d是正整数，X是t种颜色的集合。由Alice开始，Alice和Bob两个人轮流选取X中的颜色对图G的顶点进行着色，每次每人着一个顶点。如果图G的顶点x着颜色c后，由图G着颜色c的顶点导出的子图的顶点最大度至多是d，则称颜色c对顶点x来说是可行色。每次Alice和Bob必须用可行色对图G的未被着色的顶点进行着色。如果图G的所有顶点都被着色或者还有顶点没有可行色去着色，则着色结束。Alice的目标是实现对图G的所有顶点进行可行着色，而Bob的目标就是要破坏Alice实现她的目标。这篇文章主要运用分裂已着色顶点的方法证明了如果图G是二叉树，且d≥2，则x_g~((d))(G′)≤2。如果图G是树且d≥3，则x_g~((d))(G)≤2设G是外部平面图且d≥2，G′是G的2-连通的三角剖分。若T_(G′)是一条路，则x_g~((d))(G)≤5。设G是外部平面图且d≥3，G′是G的2-连通的三角剖分，D是T_(G′)的最小控制集。若T_(G′)[D]是一条路，则x_g~((d))(G)≤5。另外还讨论轮图与扇图的对策着色。 |
| 【论文题纲】 |
|
摘要 |
4-5 |
|
Abstract |
5-6 |
|
1 前言 |
6-13 |
|
1.1 基本概念 |
6-8 |
|
1.2 图的着色与对策着色 |
8-10 |
|
1.3 已有的相关结论 |
10-13 |
|
2 树上的对策色数 |
13-24 |
|
2.1 二叉树上的对策着色 |
13-21 |
|
2.2 树上放松度为3的对策色数 |
21-24 |
|
3 外部平面图上的对策着色 |
24-28 |
|
4 轮图与扇图的对策色数 |
28-31 |
|
参考文献 |
31-34 |
|
致谢 |
34 |
|
| 【DOI】 | LunWen.ID:2.2008.14458 |
