Please use this identifier to cite or link to this item: http://scholarbank.nus.edu.sg/handle/10635/102983
Title: Chromatically unique bipartite graphs with low 3-independent partition numbers
Authors: Dong, F.M.
Koh, K.M. 
Teo, K.L.
Little, C.H.C.
Hendy, M.D.
Keywords: Bipartite graph
Chromatic polynomial
Issue Date: 28-Sep-2000
Citation: Dong, F.M.,Koh, K.M.,Teo, K.L.,Little, C.H.C.,Hendy, M.D. (2000-09-28). Chromatically unique bipartite graphs with low 3-independent partition numbers. Discrete Mathematics 224 (1-3) : 107-124. ScholarBank@NUS Repository.
Abstract: For integers p,q,s with p≥q≥2 and s≥0, let script K sign-s 2 (p,q) denote the set of 2-connected bipartite graphs which can be obtained from Kp,q by deleting a set of s edges. In this paper, we prove that for any graph G ∈ script K sign-s 2 (p,q) with p≥q≥3 and 1 ≤s≤q - 1, if the number of 3-independent partitions of G is at most 2p-1 + 2q-1 + s + 2, then G is χ-unique. It follows that any graph in script K sign-s 2 (p,q) is χ-unique if p≥q≥3 and 1 ≤s≤ {q - 1, 4}. © 2000 Elsevier Science B.V. All rights reserved.
Source Title: Discrete Mathematics
URI: http://scholarbank.nus.edu.sg/handle/10635/102983
ISSN: 0012365X
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

Page view(s)

38
checked on Aug 10, 2018

Google ScholarTM

Check


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.