Coloring random graphs -- an algorithmic perspective

MaRDI QIDQ4428908zbMATH OpenFDO

Authors Michael Krivelevich

Publication date 22 September 2003

zbMATH Keywords

algorithmic random graph coloringsurvey

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Random graphs (graph-theoretic aspects) (05C80) Graph algorithms (graph-theoretic aspects) (05C85)

Recommendations

• Randomly colouring graphs (a combinatorial view)
• Coloring random graphs
• Algorithms for Colouring Random k-colourable Graphs
• Colouring random graphs in expected polynomial time
• Exact and approximative algorithms for coloring G(n,p)

Cited in

(13)

• Coloring random graphs
• Randomized Δ-edge colouring via exchanges of complex colours
• Coloring random graphs
• scientific article; zbMATH DE number 5004842 (Why is no real title available?)
• Colouring random graphs in expected polynomial time
• Randomly colouring graphs (a combinatorial view)
• Exact and approximative algorithms for coloring G(n,p)
• 随机图的$f$-染色的分类 II
• Finding Pseudorandom Colorings of Pseudorandom Graphs
• Coloring Random Intersection Graphs and Complex Networks
• MAX k‐CUT and approximating the chromatic number of random graphs
• An improved algorithm for approximating the chromatic number of \(G_{n,p}\)
• Report 7/2006: Algorithmic Graph Theory (February 12th -- February 18th, 2006)

This page was built for publication: Coloring random graphs -- an algorithmic perspective

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