Some Results On Circular Coloring And P-circular Coloring Of Graphs

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).