Colorings Of Distance Graphs And Star Extremality Of Circulant Graphs

Suppose 5 is a subset of a metric spaceμwith a metric 8 ,and D a subset of positive real numbers. The distance graph G(S,D), with a distance set D,is th graph with vertex set S in which two vertex x and y are adjacent iffδ(x,y)∈D.A k-vertex coloring of G is an assignment of k colors to all vertex of G.The coloring is peoper if any two adjacent vertexs have different colors. G is called k-vertxe colorable if it has a proper k-vertex coloring. The chromatic number x(G) of G is the minimal k for which the graph is k-vertex colorable.The circular chromatic number of a graph G is a natural generalization of the chromatic number of G.Suppose p and q are positive such that p≥2q.A (p,q)-coloring of Gis a mapping c :V(G)â†'{0,1,2,…p-1} such that ?c(x) - c(y)?|_p≥q for any edge xy in E, where ||a|| = min{a,p-a}. The circular chromatic number x_c(G) of G is theinfimum of the ratios p/q for which there exist (p,q) -colorings of G.Another generalization of the chromatic number of G is the fractional chromatic number. A fractional chromatic number of G is a mapping c from I(G),the set of allindependent sets of G ,to the interval [0,1] such that∑x(?)(G)^c(I)≥1 for all vertices x inG . The fractional number X_f{G) of G is the the infimum of the value∑I(?)(G)^c(I) of afractional coloring c of G .A graph G is Star extremal if its circular chromatic number is equal to its fractional chromatic number.Let p be a positive integer and 5 be a subset of {0,l,2,…,p-1} such that i∈S implies p-i∈S.For brevity, p-i is denoted by -i.The circulant graph G(p,S) has vertices 0,1,2,…, p -1 and i is adjacent to j if and only if i - j∈S, where subtraction is carried out modulo p .In this article, we firstly introduce the relations of the chromatic number, the circular chromatic number and the fractional chromatic number of a graph, then discuss the chromatic number, the circular chromatic number and the fractional chromatic number of one class of integer graph G(Z.D_{m,k,k+1,k+2,k+3}) (where D(m,k,k+1,k+2,k+3)={1,2,…,m}-{k,k+1,k+2,k+3}) by the methods of construction, reduction to absurdity, decomposition and enumeration. Furthermore, we introduce some conclutions on Star extremal graph and circulant graphs, and use these conclutions to prove that some classes of circulant graphs are Star extremal.