[1] Lin Wensong, Gu Guohua,. A necessary and sufficient conditionfor a vertex-transitive graph to be star extremal [J]. Journal of Southeast University (English Edition), 2004, 20 (3): 374-377. [doi:10.3969/j.issn.1003-7985.2004.03.022]

Copy

A necessary and sufficient conditionfor a vertex-transitive graph to be star extremal()

Share：

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

Volumn:

20

Issue:

2004 3

Page:

374-377

Research Field:

Mathematics, Physics, Mechanics

Publishing date:

2004-09-30

Info

Title:

A necessary and sufficient conditionfor a vertex-transitive graph to be star extremal

Author(s):

Lin Wensong;  Gu Guohua

Department of Mathematics, Southeast University, Nanjing 210096, China

Keywords:

circular chromatic number;  fractional chromatic number;  circulant graph;  star extremal graph

PACS:

C934;N945.25

DOI:

10.3969/j.issn.1003-7985.2004.03.022

Abstract:

A graph is called star extremal if its fractional chromatic number is equal to its circular chromatic number. We first give a necessary and sufficient condition for a graph G to have circular chromatic number |V(G)|/α(G)(where |V(G)| is the vertex number of G and α(G) is its independence number). From this result, we get a necessary and sufficient condition for a vertex-transitive graph to be star extremal as well as a necessary and sufficient condition for a circulant graph to be star extremal. Using these conditions, we obtain several classes of star extremal graphs.

References:

[1] Vince A. Star chromatic number [J]. J Graph Theory, 1988, 12(4): 551-559.
[2] Zhu X D. Circular chromatic number — a survey [J]. Discrete Math, 2001, 229(1-3): 371-410.
[3] Klav(ˇoverz)ar S. A note on the fractional chromatic number and the lexicographic product of graphs [J]. Discrete Math, 1998, 185(1-3): 259-263.
[4] Larsen M, Propp J, Ullman D. The fractional chromatic number of Mycielski’s graphs [J]. J Graph Theory, 1995, 19(4): 411-416.
[5] Lih K, Liu D D, Zhu X D. Star extremal circulant graphs [J]. SIAM J Discrete Math, 1999, 12(4): 491-499.
[6] Gao G, Zhu X D. Star extremal graphs and the lexicographic product [J]. Discrete Math, 1996, 152(1-3): 147-156.
[7] Lin W S. Some star extremal circulant graphs [J]. Discrete Math, 2003, 271(1-3): 169-177.

Memo

Memo:

Biography: Lin Wensong(1968—), male, associate professor, wslin@seu.edu.cn.

Common functions