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

Advanced Search
Home   
 
Browse   
Communities
& Collections
  
Issue Date   
Author   
Title   
Subject   
 
Sign on to:   
Receive email
updates
  
My Account
authorized users
  
Edit Profile   
 
Help   
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/9489

Title: Almost all graphs with 2:522n edges are not 3-colorable
Authors: Achlioptas, D.
Molloy, M.
Keywords: random graph
vertices
Issue Date: 1999
Publisher: International Press
Citation: Achlioptas, D., Molloy, M. (1999). Almost all graphs with 2:522n edges are not 3-colorable. Vol 6 (1). pp. 29DUMMY
Abstract: We prove that for c 2≥522 a random graph with n vertices and m = cn edges is not 3-colorable with probability 1 - o(1). Similar bounds for non-k-colorability are given for k > 3.
Description: published source has been acknowledged. journal website: http://www.combinatorics.org/Volume_6/v6i1toc.html
URI: http://hdl.handle.net/1807/9489
ISSN: 1077-8926
Appears in Collections:Mathematics

Files in This Item:

File Description SizeFormat
almost all graphs with 2.522.pdf231.76 kBAdobe PDF
View/Open
almost all graphs with 2.522.pdf.txt28.74 kBText
View/Open

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

uoft