| 【中文题名】 | 平方图的染色 |
| 【英文题名】 | Coloring the Square of Graphs |
| 【学科专业】 | 运筹学与控制论 |
| 【论文级别】 | 硕士论文 |
| 【投稿时间】 | 2004-10-19 |
| 【中关键词】 | 色数,L（p,q）-标号,平方图,平面图,外部平面图 |
| 【英关键词】 | chromatic number,L（p, q）-labelling,square of a graph,planar graph,outerplanar graph., |
| 【分类导航】 | 数理科学和化学>数学>代数、数论、组合理论>组合数学（组合学）>图论> |
| 【论文摘要】 | 图G的平方图，记作G~2，是一个以原图的顶点集为顶点集，若原图中两点的距离不大于2则连以边所成的图。对于正整数p，q，n与图G，如果函数φ∶V(G)→{0，1，…，n}满足如下关系：若dist_G(u，v)=1则|φ(u)-φ(v)|≥p；若dist_G(u，v)=2则|φ(u)-φ(v)|≥q，那么称函数φ为图G的L(p，q)-标号。在所有L(p，q)-标号中最小的n称为(p，q)-跨度，记作λ(G；p，q)。本文考虑了下列图类的平方图的色数范围：圈，树，Halin图，外部平面图以及不含4到9圈的平面图。对于外部平面图与不含4到9圈的平面图，本文也给出了它们(p，q)-跨度的界。根据不含4到9圈的平面图的平方图的色数范围的证明方法，本文给出了一个最多使用△+6种颜色来给该图的平方图染色的O(n~2)时间算法。最后，本文列出了一些与本文相关的有意义的没有解决的问题，作为以后研究的一个方向。 |
| 【论文题纲】 |
|
Contents |
3-4 |
|
Acknowledgements |
4-6 |
|
摘要 |
6-7 |
|
Abstract |
7-8 |
|
1 Introduction |
8-13 |
|
1.1 Basic Definitions and Terminologies |
8-9 |
|
1.2 Background and Known Results |
9-11 |
|
1.3 Main Results and Some Remarks |
11-13 |
|
2 Preliminaries |
13-18 |
|
3 Main Results |
18-34 |
|
3.1 Chromatic Number of G~2 |
18-28 |
|
3.1.1 For Trees and Halin Graphs |
18-19 |
|
3.1.2 For Outerplanar Graphs |
19-23 |
|
3.1.3 For Planar Graphs Without i-Cycles, Where 4≤i≤9 |
23-28 |
|
3.2 Generalized to L(p,q)-labelling |
28-32 |
|
3.2.1 For Outerplanar Graphs |
28-30 |
|
3.2.2 For Planar Graphs Without i-Cycles, Where 4≤i≤9 |
30-32 |
|
3.3 A bound of List Chromatic Number of G~2 |
32 |
|
3.4 An O(n~2) Time Algorithm |
32-34 |
|
4 Further Problems |
34-35 |
|
References |
35-36 |
|
| 【DOI】 | LunWen.ID:2.2008.11469 |
