On-Line Coloring of Sparse Random Graphs and Random Trees

DOI10.1006/JAGM.1996.0827MaRDI QIDQ3128993zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

greedy coloring algorithmsparse random graphs

Mathematics Subject Classification ID

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

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

Cited in

(6)

• Average-case complexity of backtrack search for coloring sparse random graphs
• Online edge coloring via tree recurrences and correlation decay
• The on-line first-fit algorithm for radio frequency assignment problems.
• Minimizing unsatisfaction in colourful neighbourhoods
• 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)