贪心染色下的随意可染色图

作者：刘赛华; 马军生

来源：河南科技大学学报(自然科学版), 2007, (01): 86-111.

• 贪心染色
• 随意可染色图
• 三正则图 Greedy coloring
• Randomly colorable graph
• 3-regular graph

贪心算法用于图的染色问题是一种简单的近似方法。采用贪心算法,证明了将图G的顶点用独立集代替后所得的图GI是随意可染色的当且仅当G本身是随意可染色图;不含K2,3的三正则图是随意可染色图当且仅当它是K4。

• 出版日期2007
• 单位中国人民解放军国防科学技术大学