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

Title: The existence of uniquely -G colourable graphs
Authors: Molloy, M.
Achlioptas, D.
Keywords: G colourable graphs
Issue Date: Jan-1998
Publisher: Elsevier
Citation: Achlioptas, D., Brown, J., Corneil, D., and Molloy,M. The existence of uniquely colourable graphs, Discrete Math. 179 (1998) 1-11.
Abstract: Given graphs F and G and a nonnegative integer k, a function π: V(F) → {1,…,k} is a -G k-colouring of F if no induced copy of G is monochromatic; F is -G k-chromatic if F has a -G k-colouring but no -G (k − 1)-colouring. Further, we say F is uniquely -G k-colourable if F is -G k-chromatic and, up to a permutation of colours, it has only one -G k-colouring. Such notions are extensions of the well-known corresponding definitions from chromatic theory. It was conjectured that for all graphs G of order at least two and all positive integers k there exist uniquely -G k-colourable graphs. We prove the conjecture and show that, in fact, in all cases infinitely many such graphs exist.
Description: The author can archive pre-print, post-print of the article. appropriate journal homepage link is attached.
URI: http://hdl.handle.net/1807/9475
ISSN: 0012-365x
Appears in Collections:Mathematics

Files in This Item:

File Description SizeFormat
g colourable graphs.pdf236.42 kBAdobe PDF

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