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/9469

Title: Colouring graph when the number of colours is almost the maximum degree
Authors: Molloy, M.
Reed, B.
Keywords: graph colouring
probabilistic method
Issue Date: 6-Jul-2001
Publisher: ACM
Citation: Molloy,M., Reed, B. Colouring Graphs whose Chromatic Number Is Almost Their Maximum Degree, Proceedings of the Third Latin American Symposium Theory of computing
Abstract: We consider for graphs of maximum degree , the problem of determining whether (G) > k for various values of k. We obtain sharp theorems characterizing when the barrier to k colourability must be a local condition, i.e. a small subgraph, and when it can be global. We also show that for large xed , this problem is either NP-complete or can be solved in linear time, and we determine precisely which values of k correspond to each case
Description: Conference Proceeding of STOC 2001.
URI: http://hdl.handle.net/1807/9469
ISBN: 1-58113-349-9
Appears in Collections:Mathematics

Files in This Item:

File Description SizeFormat
STOC 2001.pdf253 kBAdobe PDF

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