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

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

谢德政;王晓蒙;赵灿鸟

【期刊名称】《重庆理工大学学报（自然科学版）》 【年(卷),期】2011(025)003

【摘要】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.%图G的无圈着色是指正常的顶点着色,同时图中任意的圈均不着双色.换句话说,图G的无圈着色是指G的正常顶点着色并且由任意两类颜色导出的子图G'为森林.图G的无圈色数是指在G的所有无圈着色中使用色数的最小者,这里用a(G)表示.证明了最大度为5的非正则图的无圈色数最多为8,并由此推出含有割边或割点的五正则图均可以用8种颜色进行无圈着色. 【总页数】4页(108-110,117) 【关键词】无圈着色;无圈色数;最大度 【作者】谢德政;王晓蒙;赵灿鸟

【作者单位】重庆大学数理学院,重庆,400030;重庆大学数理学院,重庆,400030;重庆大学数理学院,重庆,400030