Randomly Colorable Graphs in Greedy Coloring
Sai Liu · Journal of Henan University of Science & Technology · 2007
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.