Maximum Weight Partial Colorings on Sparse Random Graphs

DOI10.1137/090755771MaRDI QIDQ3094951zbMATH OpenOpenAlexFDO

Authors Steven Jaslar, Sekhar Tatikonda

Publication date 27 October 2011

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/090755771

zbMATH Keywords

branching processcoloringsErdős-Rényi graphspartial coloringsrandom graphs

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Extremal problems in graph theory (05C35) Density (toughness, etc.) (05C42) Random graphs (graph-theoretic aspects) (05C80) Combinatorial probability (60C05) Central limit and other weak theorems (60F05) Dynamic programming (90C39)

Recommendations

• A note on coloring sparse random graphs
• Randomly coloring sparse random graphs with fewer colors than the maximum degree
• scientific article; zbMATH DE number 3895112
• scientific article; zbMATH DE number 1670678
• Max-coloring of vertex-weighted graphs
• scientific article; zbMATH DE number 1229619
• Mathematical Foundations of Computer Science 2005
• Random sampling of colourings of sparse random graphs with a constant number of colours
• Sampling random colorings of sparse random graphs

Cited in

(3)

• Central limit theorems for combinatorial optimization problems on sparse Erdős-Rényi graphs
• Randomly coloring sparse random graphs with fewer colors than the maximum degree
• scientific article; zbMATH DE number 2042286 (Why is no real title available?)

This page was built for publication: Maximum Weight Partial Colorings on Sparse Random Graphs

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