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

Title: (delta- k)-critical graphs
Authors: Molloy, M.
Reed, B.
Keywords: Delta-K critical graphs
Issue Date: Nov-2005
Publisher: Elsevier
Citation: Farzad, B., Molloy, M., Reed, B. (Delta-k)-critical graphs. J. Comb. Theory, Ser. B 93(2): 173-185, 2005
Abstract: Every graph G of maximum degree Δ is (Δ + 1)-colourable and a classical theorem of Brooks states that G is not Δ-colourable iff G has a (Δ + 1)-clique or Δ = 2 and G has an odd cycle. Reed extended Brooks' Theorem by showing that if Δ (G) ≥ 10 14 then G is not (Δ - 1)-colourable iff G contains a Δ-clique. We extend Reed's characterization of (Δ - 1)-colourable graphs and characterize (Δ - 2), (Δ - 3), (Δ - 4) and (Δ - 5)-colourable graphs, for sufficiently large Δ, and prove a general structure for graphs with χ close to Δ. We give a linear time algorithm to check the (Δ - k)-colourability of a graph, for sufficiently large Δ and any constant k. © 2004 Elsevier Inc. All rights reserved.
Description: Author can archive pre-print and post-print of the journal article with approporiate journal homepage link attached.
URI: http://hdl.handle.net/1807/9476
Appears in Collections:Mathematics

Files in This Item:

File Description SizeFormat
babak-2.pdf267.15 kBAdobe PDF

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