For two integers k and d with （k, d） = 1 and k≥2d, let G^dk be the graph with vertex set {0,1,…k - 1 } in which ij is an edge if and only if d≤｜ i -j I｜≤k - d. The circular chromatic number χc（G） of a graph...For two integers k and d with （k, d） = 1 and k≥2d, let G^dk be the graph with vertex set {0,1,…k - 1 } in which ij is an edge if and only if d≤｜ i -j I｜≤k - d. The circular chromatic number χc（G） of a graph G is the minimum of k/d for which G admits a homomorphism to G^dk. The relationship between χc（ G- v） and χc （G）is investigated. In particular, the circular chromatic number of G^dk - v for any vertex v is determined. Some graphs withx χc（G - v） =χc（G） - 1 for any vertex v and with certain properties are presented. Some lower bounds for the circular chromatic number of a graph are studied, and a necessary and sufficient condition under which the circular chromatic number of a graph attains the lower bound χ- 1 ＋ 1/α is proved, where χ is the chromatic number of G and a is its independence number.展开更多
The circular chromatic number and the fractional chromatic number are two generalizations of the ordinary chromatic number of a graph. We say a graph G is star extremal if its circular chromatic number is equal to its...The circular chromatic number and the fractional chromatic number are two generalizations of the ordinary chromatic number of a graph. We say a graph G is star extremal if its circular chromatic number is equal to its fractional chromatic number. This paper gives an improvement of a theorem. And we show that several classes of circulant graphs are star extremal.展开更多
The circular chromatic number and the fractional chromatic number are two generalizations of the ordinary chromatic number of a graph. A graph is called star extremal if its fractional chromatic number equals to its c...The circular chromatic number and the fractional chromatic number are two generalizations of the ordinary chromatic number of a graph. A graph is called star extremal if its fractional chromatic number equals to its circular chromatic number (also known as the star chromatic number). This paper studies the star extremality of the circulant graphs whose generating sets are of the form {±1,±k} .展开更多
The circular chromatic number of a graph is an important parameter of a graph. The distance graph G(Z,D) , with a distance set D , is the infinite graph with vertex set Z={0,±1,±2,...} in which tw...The circular chromatic number of a graph is an important parameter of a graph. The distance graph G(Z,D) , with a distance set D , is the infinite graph with vertex set Z={0,±1,±2,...} in which two vertices x and y are adjacent iff y-x∈D . This paper determines the circular chromatic numbers of two classes of distance graphs G(Z,D m,k,k+1 ) and G(Z,D m,k,k+1,k+2 ).展开更多
基金The National Natural Science Foundation of China(No.10671033)
文摘For two integers k and d with （k, d） = 1 and k≥2d, let G^dk be the graph with vertex set {0,1,…k - 1 } in which ij is an edge if and only if d≤｜ i -j I｜≤k - d. The circular chromatic number χc（G） of a graph G is the minimum of k/d for which G admits a homomorphism to G^dk. The relationship between χc（ G- v） and χc （G）is investigated. In particular, the circular chromatic number of G^dk - v for any vertex v is determined. Some graphs withx χc（G - v） =χc（G） - 1 for any vertex v and with certain properties are presented. Some lower bounds for the circular chromatic number of a graph are studied, and a necessary and sufficient condition under which the circular chromatic number of a graph attains the lower bound χ- 1 ＋ 1/α is proved, where χ is the chromatic number of G and a is its independence number.
文摘The circular chromatic number and the fractional chromatic number are two generalizations of the ordinary chromatic number of a graph. We say a graph G is star extremal if its circular chromatic number is equal to its fractional chromatic number. This paper gives an improvement of a theorem. And we show that several classes of circulant graphs are star extremal.
文摘The circular chromatic number and the fractional chromatic number are two generalizations of the ordinary chromatic number of a graph. A graph is called star extremal if its fractional chromatic number equals to its circular chromatic number (also known as the star chromatic number). This paper studies the star extremality of the circulant graphs whose generating sets are of the form {±1,±k} .
文摘The circular chromatic number of a graph is an important parameter of a graph. The distance graph G(Z,D) , with a distance set D , is the infinite graph with vertex set Z={0,±1,±2,...} in which two vertices x and y are adjacent iff y-x∈D . This paper determines the circular chromatic numbers of two classes of distance graphs G(Z,D m,k,k+1 ) and G(Z,D m,k,k+1,k+2 ).
