A note on coloring sparse random graphs

DOI10.1016/J.DISC.2008.09.038MaRDI QIDQ1025963zbMATH OpenOpenAlexFDO

Authors C. Sommer

Publication date 23 June 2009

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.disc.2008.09.038

zbMATH Keywords

analysis of algorithmscombinatorial problemsgraph coloring algorithmrandom graphsgenerating function

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 1962838
• Mathematical Foundations of Computer Science 2005
• Randomly coloring sparse random graphs with fewer colors than the maximum degree
• Exact and approximative algorithms for coloring G(n,p)
• Sequential and distributed graph coloring algorithms with performance analysis in random graph spaces

Cites work

• scientific article; zbMATH DE number 3168330 (Why is no real title available?)
• scientific article; zbMATH DE number 3574966 (Why is no real title available?)
• 3-coloring in time
• A note on the complexity of the chromatic number problem
• A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
• Exact and approximative algorithms for coloring G(n,p)
• Random Graphs
• Sudden emergence of a giant \(k\)-core in a random graph
• Zero knowledge and the chromatic number

Cited in

(12)

• A GRASP for coloring sparse graphs
• Average-case complexity of backtrack search for coloring sparse random graphs
• Graph coloring in the estimation of sparse derivative matrices: Instances and applications
• Randomly coloring sparse random graphs with fewer colors than the maximum degree
• Chromatic thresholds in sparse random graphs
• Maximum Weight Partial Colorings on Sparse Random Graphs
• scientific article; zbMATH DE number 5279368 (Why is no real title available?)
• Uncertain vertex coloring problem
• scientific article; zbMATH DE number 1670678 (Why is no real title available?)
• Coloring Clique-free Graphs in Linear Expected Time
• An uncertain chromatic number of an uncertain graph based on \(\alpha \)-cut coloring
• Computing the eccentricity distribution of large graphs

This page was built for publication: A note on coloring sparse random graphs

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