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

顶点可迁图为star extremal的一个充要条件(英文)

作　　者：林文松[1] 顾国华[1] 

机构地区：[1]东南大学数学系,南京210096

出　　处：《Journal of Southeast University(English Edition)》2004年第3期374-377,共4页东南大学学报（英文版）

基　　金：TheNationalNaturalScienceFoundationofChina(No .10 1710 13 ) .

摘　　要：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.一个图当它的圆色数和分色数相等称之为starextremal.本文首先给出一个图的圆色数等于顶点数除以独立数的充要条件 .然后利用这个结果给出了顶点可迁图是starextremal的一个充要条件 .并由此得到了几类新的starextremal图 .

关 键 词：circular chromatic number fractional chromatic number circulant graph star extremal graph 

分 类 号：O157.5[理学—数学]