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

Title: A bound on the chromatic number of the square of a planar graph
Authors: Molloy, M.
Salavatipour, M.
Keywords: chromatic number
square of a planar graph
Issue Date: Jul-2005
Publisher: Elsevier
Citation: Molloy, M., Salavatipour, M. R. A bound on the chromatic number of the square of a planar graph, J. Combin. Theory Ser. B 94 (2005) 189-213
Abstract: Wegner conjectured that the chromatic number of the square of any planar graph G with maximum degree Δ ≥ 8 is bounded by χ(G2) ≤ ⌊3/2 Δ⌋ + 1. We prove the bound χ(G2) ≤ ⌈5/3 Δ⌉ + 78. This is asymptotically an improvement on the previously best-known bound. For large values of Δ we give the bound of χ(G2) ≤ ⌈5/3 Δ⌉ + 25. We generalize this result to L(p,q)-labeling of planar graphs, by showing that λqp (G) ≤ q ⌈5/3 Δ⌉ + 18p + 77q - 18. For each of the results, the proof provides a quadratic time algorithm. © 2005 Elsevier Inc. All rights reserved
Description: The author can archive pre-print, post-print of the article. appropriate journal homepage link is attached.
URI: http://hdl.handle.net/1807/9473
Appears in Collections:Mathematics

Files in This Item:

File Description SizeFormat
chromatic number of the square of a planar graph.pdf377.13 kBAdobe PDF

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