On-Line Coloring of Sparse Random Graphs and Random Trees

DOI10.1006/JAGM.1996.0827zbMATH Open0866.68075OpenAlexW2034589411MaRDI QIDQ3128993FDOQ3128993

Authors: Robert S. Weishaar, Boris 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

Recommendations

• Randomized online graph coloring
• Sequential and distributed graph coloring algorithms with performance analysis in random graph spaces
• Randomly coloring sparse random graphs with fewer colors than the maximum degree
• On-line and first fit colorings of graphs

zbMATH Keywords

greedy coloring algorithmsparse random graphs

Mathematics Subject Classification ID

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

Cited In (6)

• Average-case complexity of backtrack search for coloring sparse random graphs
• Online edge coloring via tree recurrences and correlation decay
• Minimizing unsatisfaction in colourful neighbourhoods
• The on-line first-fit algorithm for radio frequency assignment problems.
• Sequential and distributed graph coloring algorithms with performance analysis in random graph spaces
• Generalized random sequential adsorption on Erdős-Rényi random graphs

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

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