Randomly colorable graphs in greedy coloring

MaRDI QIDQ3517847zbMATH OpenFDO

Authors Saihua Liu, Junsheng Ma

Publication date 6 August 2008

zbMATH Keywords

greedy coloring3-regular graphrandomly 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)

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