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

Randomly Colorable Graphs in Greedy Coloring

贪心算法用于图的染色问题是一种简单的近似方法。采用贪心算法,证明了将图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.