[1] Wu Jianzhuan, Lin Wensong,. Some results on circular chromatic number of a graph [J]. Journal of Southeast University (English Edition), 2008, 24 (2): 253-256. [doi:10.3969/j.issn.1003-7985.2008.02.027]

Copy

Some results on circular chromatic number of a graph()

图的圆色数的一些结果

Share：

Journal of Southeast University (English Edition)[ISSN:1003-7985/CN:32-1325/N]

Volumn:

24

Issue:

2008 2

Page:

253-256

Research Field:

Mathematics, Physics, Mechanics

Publishing date:

2008-06-03

Info

Title:

Some results on circular chromatic number of a graph

图的圆色数的一些结果

Author(s):

Wu Jianzhuan;  Lin Wensong

Department of Mathematics, Southeast University, Nanjing 211189, China

吴建专;  林文松

东南大学数学系, 南京 211189

Keywords:

(k;  d)-coloring;  r-circular-coloring;  circular chromatic number;  Mycielski’s graph

(k;  d)-着色;  r-圆着色;  圆色数;  Mycielski图

PACS:

O157.5

DOI:

10.3969/j.issn.1003-7985.2008.02.027

Abstract:

For two integers k and d with(k, d)=1 and k≥2d, let G^d_k be the graph with vertex set {0, 1, …, k-1} in which ij is an edge if and only if d≤|i-j|≤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^d_k.The relationship between χ_c(G-v)and χ_c(G)is investigated.In particular, the circular chromatic number of G^d_k-v for any vertex v is determined.Some graphs with χ_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 α is its independence number.

设k和d是2个互素的正整数且k≥2d.G^d_k 是一个图, 它的顶点集合为{0, 1, …, k-1}, 边集合为{ij|d≤|i-j≤k-d, i, j=0, 1, …, k-1}.图G的圆色数χ_c(G)定义为使得图G与G^d_k 同态的2个正整数k和d的最小比值k/d.研究了χ_c(G)和χ_c(G-v)之间的关系, 对任意顶点v求出了χ_c(G^d_k-v)的精确值, 给出了具有对任意顶点χ_c(G-v)=χ_c(G)-1和其他特定性质的图类;并对图的圆色数的一些下界进行了探讨, 给出了图的圆色数达到下界χ-1+1/α的充要条件, 这里χ和α分别是图G的点色数和独立数.

References:

[1] Vince A.Star chromatic number [J].J Graph Theory, 1988, 12(4):551-559.
[2] Bondy J A, Hell P.A note on the star chromatic number [J].J Graph Theory, 1990, 14(4):479-482.
[3] Zhu X.Circular chromatic number—a survey [J].Discrete Math, 2001, 229(1/2/3):371-410.
[4] Zhou B.Some theorems concerning the star chromatic number of a graph [J].J Combin Theory Ser B, 1997, 70(2):245-258.
[5] Zhu X.Star chromatic number and products of graphs [J].J Graph Theory, 1992, 16(6):557-569.
[6] Golumbic M C.Algorithmic graph theory and perfect graphs [M].Academic Press, 1980.
[7] Hossein H, Zhu X.Circular chromatic number of subgraphs [J].J Graph Theory, 2003, 44(2):95-105.
[8] Mycielski J.Sur le coloriage des graphes [J].Colloq Math, 1995, 3(1):161-162.
[9] Chang G J, Huang L, Zhu X.Circular chromatic numbers of Mycielski’s graphs [J].Discrete Math, 1999, 205(1/2/3):23-27.
[10] Lam P C B, Lin W S, Gu G H, et al.Circular chromatic number and a generalization of the construction of mycielski [J].J Combin Theory Ser B, 2003, 89(2):195-205.

Memo

Memo:

Biography: Wu Jianzhuan(1970—), female, associate professor, jzwujz@yahoo.com.cn.
Foundation item: The National Natural Science Foundation of China(No.10671033).
Citation: Wu Jianzhuan, Lin Wensong.Some results on circular chromatic number of a graph[J].Journal of Southeast University(English Edition), 2008, 24(2):253-256.

Common functions