| 【中文题名】 | 图的圆着色及p-圆着色的若干结论 |
| 【英文题名】 | Some Results on Circular Coloring and P-circular Coloring of Graphs |
| 【学科专业】 | 运筹学与控制论 |
| 【论文级别】 | 硕士论文 |
| 【投稿时间】 | 2006-10-27 |
| 【中关键词】 | 性质P,P着色,圆着色,P-圆着色,临界图,连通度 |
| 【英关键词】 | properity P,P coloring,circular coloring,P-circular coloring,a critical graph,connectivity, |
| 【分类导航】 | 数理科学和化学>数学>代数、数论、组合理论>组合数学（组合学）>图论> |
| 【论文摘要】 | 圆色数是由Vince首次提出的，是对色数的一个推广。对于任意ε＞0，是否存在具有高连通性的临界图使得它的圆色数接近它的色数?在这篇论文，我们继续Steffen和Zhu的讨论，弥补了他们讨论中的一处小的遗漏，从而完善了他们的结论，即对于任意整数m≥3，k≥2，总存在m-连通(m+1)-临界图H(m，k)使得x_c(H(m，k))≤m+1／k。
设P是一个非平凡的具有传递性的性质，Harary首次提出P着色的概念，也就是条件着色，同时这一概念也得到了广泛研究。本论文，我们引入P-圆着色的定义：令k和d为正整数，图G的一个(P，k，d)-着色是一个从V(G)到Z_k的映射，使得对任意整数i，G∈P；同时给出等价定义并有如下简单的结论：
1．设(X_0，X_1，…，X_(k-1))为图G的一个(P，k，d)-着色，其中正整数k和d互素。如果存在某个整数t，使得X_t=φ，那么x_c(G∶P)＜k／d。
2．设x(G∶P)=t，如果存在非空子集A(?)V(G)使得对图G的任一(P，t)-着色c下的任一色类F总有F(?)A或F∩A=φ，那么x_c(G∶... |
| 【论文题纲】 |
|
Contents |
3-4 |
|
Abstract in English |
4-5 |
|
摘要 |
5-6 |
|
Preface |
6-9 |
|
1 A kind of critical graphs with x_c(G) closing to x(G) |
9-16 |
|
2 P-circular coloring of a graph |
16-28 |
|
3 Further research |
28-30 |
|
Bibliography |
30-34 |
|
Acknowledgements |
34 |
|
| 【DOI】 | LunWen.ID:2.2008.11751 |
