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

Randomly Colorable Graphs in Greedy Coloring

作　　者：刘赛华[1] 马军生[2] 

机构地区：[1]兰州大学数学与统计学院,甘肃兰州730000 [2]西安通信学院一系,陕西西安710106

出　　处：《河南科技大学学报（自然科学版）》2007年第1期86-89,共4页Journal of Henan University of Science And Technology:Natural Science

基　　金：国家自然科学基金项目(10471058)

摘　　要：贪心算法用于图的染色问题是一种简单的近似方法。采用贪心算法,证明了将图G的顶点用独立集代替后所得的图GI是随意可染色的当且仅当G本身是随意可染色图;不含K2,3的三正则图是随意可染色图当且仅当它是K4。Greedy algorithm is a simple approximative method in graph coloring.By greedy algorithm,a graph which was obtained from G by substituting vertices in G with independent sets is randomly colorable if and only if G itself is randomly colorable.It is also proved that a connected cubic graph without its subgraph is randomly colorable if and only if K_4 is randomly colorable.

关 键 词：贪心染色 随意可染色图 三正则图 

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