Randomly colorable graphs in greedy coloring

zbMATH Open1150.05338MaRDI QIDQ3517847FDOQ3517847

Authors: Saihua Liu, Junsheng Ma 

Publication date: 6 August 2008

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

zbMATH Keywords

greedy coloring3-regular graphrandomly colorable graph

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Cited In (9)

• Title not available (Why is that?)
• 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)