Maximum Weight Partial Colorings on Sparse Random Graphs

DOI10.1137/090755771zbMath1294.05074OpenAlexW2095015407MaRDI QIDQ3094951

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

random graphsbranching processcoloringsErdős-Rényi graphspartial colorings

Mathematics Subject Classification ID

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

Related Items (1)

Central limit theorems for combinatorial optimization problems on sparse Erdős-Rényi graphs

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