Randomly colorable graphs in greedy coloring

MaRDI QIDQ3517847zbMATH OpenFDO

Authors Saihua Liu, Junsheng Ma

Publication date 6 August 2008

zbMATH Keywords

3-regular graphgreedy coloringrandomly colorable graph

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Recommendations

• The greedy coloring is a bad probabilistic algorithm
• scientific article; zbMATH DE number 5859
• scientific article; zbMATH DE number 4134072
• Algorithms for Colouring Random k-colourable Graphs
• Almost all k-colorable graphs are easy to color

Cited in

(9)

• Non-independent randomized rounding and coloring
• scientific article; zbMATH DE number 1688362 (Why is no real title available?)
• Coloring random graphs
• Randomized Δ-edge colouring via exchanges of complex colours
• Coloring random graphs
• Randomly coloring random graphs
• Randomly colouring graphs (a combinatorial view)
• Randomly Coloring Regular Bipartite Graphs and Graphs with Bounded Common Neighbors
• Finding Pseudorandom Colorings of Pseudorandom Graphs

This page was built for publication: Randomly colorable graphs in greedy coloring

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3517847)