On-Line Coloring of Sparse Random Graphs and Random Trees

DOI10.1006/JAGM.1996.0827zbMath0866.68075OpenAlexW2034589411MaRDI QIDQ3128993

Robert S. Weishaar, Boris G. Pittel

Publication date: 27 April 1997

Published in: Journal of Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1006/jagm.1996.0827

zbMATH Keywords

greedy coloring algorithmsparse random graphs

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Related Items (3)

Average-case complexity of backtrack search for coloring sparse random graphs ⋮ Generalized random sequential adsorption on Erdős-Rényi random graphs ⋮ The on-line first-fit algorithm for radio frequency assignment problems.

This page was built for publication: On-Line Coloring of Sparse Random Graphs and Random Trees