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 notion of the star chromatic number of a graph is a generalization of the chromatic number. In this paper. we calculate the star chromatic numbers of three infinite families of planar graphs. The first two familie...The notion of the star chromatic number of a graph is a generalization of the chromatic number. In this paper. we calculate the star chromatic numbers of three infinite families of planar graphs. The first two families are derived from a 3-or 5-wheel by subdivisions. their star chromatic numbers being 2+2/(2n + 1). 2+3/(3n + 1)and 2+3/ (3n - 1), respectively. The third family of planar graphs are derived from n odd wheels by Hajos construction with star chromatic numbers 3 + 1/n. which is a generalization of one resnlt of Gao et al.展开更多
基金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 notion of the star chromatic number of a graph is a generalization of the chromatic number. In this paper. we calculate the star chromatic numbers of three infinite families of planar graphs. The first two families are derived from a 3-or 5-wheel by subdivisions. their star chromatic numbers being 2+2/(2n + 1). 2+3/(3n + 1)and 2+3/ (3n - 1), respectively. The third family of planar graphs are derived from n odd wheels by Hajos construction with star chromatic numbers 3 + 1/n. which is a generalization of one resnlt of Gao et al.
