高度正则图的全着色

原文传递

导出

摘要一个图G的全色数XT(G)是对G的边和顶点着色的最小数,使得相关联或相邻元素着不同色.证明了如果G是正则图并且d(G)≥2/3|V(G)|+(23)/6,这里d(G)表示在G中顶点的度,则XT(G)≤d(G)+2.

作者谢德政杨万年

机构地区重庆大学数理学院

出处《中国科学（A辑）》 CSCD 北大核心 2008年第10期1183-1200,共18页 Science in China(Series A)

基金重庆市科委自然科学基金计划(批准号:CSTC 2007BB2123)资助项目

关键词全色数全着色全着色猜想

参考文献20

1Behzad M. Graphs and their chromatic numbers. Doctoral thesis, Michigan State University, 1965
2Vizing V G. Some unsolved problems in graph theory. Russ Math Surv, 23:125-142 (1968)
3Behzad M, Chartrand G, Cooper Jr J K. The colour numbers of complete graphs. J Lond Math Soc, 42: 225-228 (1967)
4Chew K H, Yap H P. Total chromatic number and chromatic index of complete r-partite graphs. J Graph Theory, 16:629-634 (1992)
5Kostochka A V. The total coloring of a multigraph with maximal 4. Discret Math, 17:161-163 (1977)
6Kostochka A V. The total chromatic number of any multigraph with maximum degree five is at most seven. Discret Math, 162:199-214 (1996)
7Vijayaditya N. On total chromatic number of a graph, J Lond Math Soc, 3:405-108 (1971)
8Borodin O V. On the total coloring of planar graphs. J Reine Angew Math, 394:180-185 (1989)
9Yap H P. Total-colourings of graphs. Manuscript, 1989
10Andersen L. Total colouring of simple graphs (in Danish). Master's thesis, University of Aalborg, 1993

中国科学（A辑）

2008年第10期

内容加载中请稍等...