【作者】 杨海燕；

【导师】 许宝刚；

【作者基本信息】 南京师范大学 ， 运筹学与控制论， 2006， 硕士

【摘要】 圆色数是由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，<（?）π^-（i）>G∈P；同时给出等价定义并有如下简单的结论： 1．设(X₀，X₁，…，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∶P）=x（G∶P）。更多还原

【Abstract】 The circular chromatic number is a generalization of the chromatic number, and it was first introduced by Vince with the name the star chromatic number. Let ε > 0 be a positive number, does there exists a critical graph G of high connectivity such that Xc（G） ≤ x（G） - 1 + ε? Steffen and Zhu answered this question almost completely, where some marginal situations are left. In this thesis, we continue their research and resolve the left margine. So far, we answer the question completely.Let P be a hereditary and nontrivial property, Harary first introduced the concept of P coloring （conditional coloring）. The concept was studied extensively since then. In this thesis, we generalized P coloring to P-circular coloring （let k and d be positive integers, a （P, k, d）-coloring of G is a function c from V（G） to Z_k suchthat ∈ P for any integer i）, and then give some equivalent definitions of it. In the end, we get some suffient conditions about X_c（G : P）=x（G : P）, e.g.1 Let (X₀, X₁,...,X_k-1) be a （P,k, d）-partition of G where gcd（k, d） = 1. If X_t = （?） for some t, then X_c（G : P）< k/d.2 Let x（G : P）= t. If there is a nonempty proper subset A of V（G） such that for any （P,t）-coloring c of G, and for any color class F of c, either F （?） A or F∩A = （?）, then X_c（G : P）= x（G : P）.更多还原