test Browse by Author Names Browse by Titles of Works Browse by Subjects of Works Browse by Issue Dates of Works

Advanced Search
& Collections
Issue Date   
Sign on to:   
Receive email
My Account
authorized users
Edit Profile   
About T-Space   

T-Space at The University of Toronto Libraries >
University of Toronto at Scarborough >
Computer and Mathematical Science >
Mathematics >

Please use this identifier to cite or link to this item: http://hdl.handle.net/1807/9485

Title: Analysis of a list-coloring algorithm on a random graph
Authors: Achlioptas, D.
Molloy, M.
Keywords: coloring algorithm
andom graphs
Issue Date: 19-Oct-1997
Publisher: IEEE Computer Society
Citation: Achlioptas, D., Molloy, M. (1997). Analysis of a List-colouring algorithm on a Random Graph. Proceedings of Annual Symposium on Foundations of Computer Science
Abstract: We introduce a natural k-coloring algorithm and analyze its performance on random graphs with constant expected degree c (Gn,p = c/n). For k = 3 our results imply that almost all graphs with n vertices and 1.923 n edges are 3-colorable. This improves the lower bound on the threshold for random 3-colorability significantly and settles the last case of a long-standing open question of Bollobas. We also provide a tight asymptotic analysis of the algorithm. We show that for all k≥3, if c≤k ln k-3/2k then the algorithm almost surely succeeds, while for any ε>0, and k sufficiently large, if c≥(1+ε)k ln k then the algorithm almost surely fails. The analysis is based on the use of differential equations to approximate the mean path of certain Markov chains.
Description: conference website http://www.informatik.uni-trier.de/~ley/db/conf/focs/focs97.html ©1997 IEEE.
URI: http://hdl.handle.net/1807/9485
ISSN: 0272-5428
Appears in Collections:Mathematics

Files in This Item:

File Description SizeFormat
focs1997.pdf258.89 kBAdobe PDF
focs1997.pdf.txt47.03 kBText

Items in T-Space are protected by copyright, with all rights reserved, unless otherwise indicated.