平面图的循环色数及临界性  

Circular Chromatic Number and Criticality of Planar Graphs

作　　者：李珍萍[1] 闫桂英[2] 

机构地区：[1]北京物资学院数理系,北京101149 [2]中国科学院数学与系统科学研究院,北京100080

出　　处：《应用数学学报》2006年第6期972-983,共12页Acta Mathematicae Applicatae Sinica

基　　金：香港王宽诚博士后奖励基金资助项目.

摘　　要：循环着色是普通着色的推广．本文中,我们研究了一类平面图-“花图”的循环着色问题,证明了由2r+1个长为2n+1的圈构成的“辐路”长度为m的花图Fr,m,n的循环色数是2+1/(n-m/2),并证明了在这类图中去掉任何一个点或边后,循环色数都严格减少但普通色数不减少,即这类图是循环色临界的但不是普通色临界的．同时,我们还研究了循环着色与图Gkd中的链之间的关系,给出了两个等价的条件．Circular coloring is a generalization of the ordinary coloring. In this paper, we investigate the circular coloring problem of an infinite family planar graphs Fτ1,m,n-the flower graph which is constructed by stick 2r ＋ 1 odd cycles of length 2n ＋ 1 to form a spoke path of length m. We first proved that the circular chromatic number of Fτ m ,n is 2＋1/n-m/2Then we prove that after deleting any vertex or edge of Fτ,m,n, the circular chromatic number will be strictly decreased, but the ordinary chromatic number will not be decreased. That is, this kind of graphs is circular color critical but not color critical. Meanwhile, we investigate the relationship between the circular coloring and the walks of graph Gd, and give two equal conditions.

关 键 词：循环色数 临界 有向图 平面图 

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