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

摘要：

图G的无圈着色是指正常的顶点着色,同时图中任意的圈均不着双色.换句话说,图G的无圈着色是指G的正常顶点着色并且由任意两类颜色导出的子图G'为森林.图G的无圈色数是指在G的所有无圈着色中使用色数的最小者,这里用a(G)表示.证明了最大度为5的非正则图的无圈色数最多为8,并由此推出含有割边或割点的五正则图均可以用8种颜色进行无圈着色.

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

所属期刊栏目：25

分类号：O157.5(代数、数论、组合理论)

在线出版日期：2011-08-08（万方平台首次上网日期，不代表论文的发表时间）

页数：共4页

页码：108-110,117