图的圆着色及p-圆着色的若干结论

摘要

圆色数是由Vince首次提出的，是对色数的一个推广.对于任意ε＞0，是否存在具有高连通性的临界图使得它的圆色数接近它的色数?在这篇论文，我们继续Steffen和Zhu的讨论，弥补了他们讨论中的一处小的遗漏，从而完善了他们的结论，即对于任意整数m≥3，k≥2，总存在m-连通(m+1)-临界图H(m，k)使得Xc(H(m，k))≤m+1/k. 设P是一个非平凡的具有传递性的性质，Harary首次提出P着色的概念，也就是条件着色，同时这一概念也得到了广泛研究.本论文中，我们引入P-圆着色的定义：令k和d为正整数，图G的一个(P，k，d)-着色是一个从V(G)到Zk的映射，使得对任意整数i，(i+d-1∪iπ-(i))G∈P；同时给出等价定义并有如下简单的结论： 1.设(X0，X1，………，Xk-1)为图G的一个(P，k，d)-着色，其中正整数k和d互素.如果存在某个整数t，使得Xt=Φ，那么Xc(G∶P)＜k/d. 2.设X(G∶P)=t，如果存在非空子集A()V(G)使得对图G的任一(P，t)-着色c下的任一色类F总有F()A或F∩A=Φ，那么Xc(G∶P)=X(G∶P).

目录

摘要

Preface

Chapter1 A kind of critical graphs with χc(G) closing to χ(G)

Chapter2 P-circular coloring of a graph

Chapter3 Further research

Bibliography

Acknowledgements