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

Title: Colouring a graph frugally
Authors: Hind, H.
Molloy, M.
Reed, B.
Keywords: colouring a graph frugally
Issue Date: Dec-1997
Publisher: Springer Verlag
Citation: Hind H., Molloy M. and Reed B. Colouring a graph frugally; Combinatorica Vol. 17, 1997, 469-482.
Abstract: We prove that any graph with maximum degree Delta sufficiently large, has a proper vertex colouring using a Delta + 1 colours such that each colour class appears at most log(8) Delta times in the neighbourhood of any vertex. We also show that for beta greater than or equal to 1, the minimum number of colours required to colour any such. graph so that each vertex appears at most beta times in the neighbourhood of any vertex is theta(Delta + Delta(1+1/beta)/beta), showing in particular that when beta = log Delta/loglog Delta, such a colouring cannot always be achieved with O(Delta) colours. We also provide a polynomial time algorithm to find such a colouring. This has applications to the total chromatic number of a graph.
Description: Author's own final version can be archived.Must link the journal to publisher's website.
URI: http://hdl.handle.net/1807/9472
ISSN: 0209-9683
Appears in Collections:Mathematics

Files in This Item:

File Description SizeFormat
colouring a graph frugally 2.pdf634.25 kBAdobe PDF

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