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 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. 展开更多
For two positive integers k and d such that k ≥ 2d, Gkd is the graph with vertex set {0,1, ...,k-1} in which ij is an edge if and only if d ≤ |i-j| ≤ k-d. Clearly, Gk1 is a complete graph of k vertices and we alway...For two positive integers k and d such that k ≥ 2d, Gkd is the graph with vertex set {0,1, ...,k-1} in which ij is an edge if and only if d ≤ |i-j| ≤ k-d. Clearly, Gk1 is a complete graph of k vertices and we always assume d ≥ 2 in the following. It is easy to see (also [1]) that a graph G is (k, d)-colorable if and only if there exists a homomorphism from G to Gkd.展开更多
文摘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 ).
文摘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.
基金NSFC(No.60172003) Natural Science Foundation of Shandong Province(No.Z2000A02).
文摘For two positive integers k and d such that k ≥ 2d, Gkd is the graph with vertex set {0,1, ...,k-1} in which ij is an edge if and only if d ≤ |i-j| ≤ k-d. Clearly, Gk1 is a complete graph of k vertices and we always assume d ≥ 2 in the following. It is easy to see (also [1]) that a graph G is (k, d)-colorable if and only if there exists a homomorphism from G to Gkd.
