圈的推广Mycielski图的圆色数(英文)  

CIRCULAR CHROMATIC NUMBERS OF THE GENERALIZED MYCIELSKIANS OF CYCLES

作　　者：林文松[1] 林子波[2] 邵慰慈[2] 

机构地区：[1]东南大学数学系,南京210096 [2]香港浸会大学数学系

出　　处：《南京大学学报（数学半年刊）》2006年第2期232-241,共10页Journal of Nanjing University(Mathematical Biquarterly)

基　　金：Supported by NSFC under grant 10671033 and Southeast University Science Foundation XJ0607230.

摘　　要：Mycielski图是1955年由Mycielski提出来的．任给一个图G和一个非负整数m,G的推广Mycielski图μm(G)是G的Mycielski图的一个自然的推广．推广Mycielski图的性质以及它们的点色数、圆色数和分数色数等已有许多研究．本文研究圈的推广Mycielski图的圆色数．定义Cn为n个顶点的圈．对任意非负整数m和大于2的整数n,本文确定了图μm(Cn)的圆色数,同时还得到了图μm(Cn)-v的圆色数的一些结果．Generalized Mycielski＇s graphs （also known as cones over graphs） are the natural generalization of Mycielski＇s graphs （which were first introduced by Mycielski [16]in 1955）. Given a graph G and any integer m ≥ 0, one can transform G into a new graph μm（G）, the generalized Mycielskian of G. Many basic properties of μm（G） were established in [14,19]. And the circular chromatic numbers of the generalized Mycielskians of complete graphs were completely determined in [12]. Here we determine the circular chromatic numbers of μm（Cn） for any m 〉 0 and n ≥ 3, where Cn is the cycle of length n. We also investigate the circular chromatic numbers of μm（Cn） -v for each vertex v of μm（G）. For m ≥ 1 and odd n（〉 5）, the graphs μm（Cn） turn out to be 4-critical, triangle-free graphs with Xc = χ = 4. Furthermore the odd girth of graphs μm（Cn） can be arbitrarily large.

关 键 词：圆色数 推广Mycielski图 圈 奇围长 临界图 

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