最大度为5的非正则图的无圈着色  

Acyclic Coloring of Non-regular Graphs of Maximum Degree Five

作　　者：谢德政[1] 王晓蒙[1] 赵灿鸟[1] 

机构地区：[1]重庆大学数理学院,重庆400030

出　　处：《重庆理工大学学报（自然科学）》2011年第3期108-110,117,共4页Journal of Chongqing University of Technology：Natural Science

摘　　要：图G的无圈着色是指正常的顶点着色,同时图中任意的圈均不着双色。换句话说,图G的无圈着色是指G的正常顶点着色并且由任意两类颜色导出的子图G'为森林。图G的无圈色数是指在G的所有无圈着色中使用色数的最小者,这里用a(G)表示。证明了最大度为5的非正则图的无圈色数最多为8,并由此推出含有割边或割点的五正则图均可以用8种颜色进行无圈着色。An acyclic coloring of graph G is a proper coloring of such that there are no bi-colored cycles.In other words,an acyclic coloring of graph G′ is a proper coloring of G′ such that any two classes of colors induced a graph G′ which is a forest（that is,an acyclic graph）.The minimum number of colors necessary to acyclically color G is called acyclic chromatic number of G,which is denoted by a（G）.In this paper,any non-regular graph of maximum degree 5 has acyclic chromatic number at most 8,also,we deduced that if G has cut edges or cut vertices,then a（G）≤8.

关 键 词：无圈着色 无圈色数 最大度 

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