Please use this identifier to cite or link to this item:
https://scholarbank.nus.edu.sg/handle/10635/102824
DC Field | Value | |
---|---|---|
dc.title | An attempt to classify bipartite graphs by chromatic polynomials | |
dc.contributor.author | Dong, F.M. | |
dc.contributor.author | Koh, K.M. | |
dc.contributor.author | Teo, K.L. | |
dc.contributor.author | Little, C.H.C. | |
dc.contributor.author | Hendy, M.D. | |
dc.date.accessioned | 2014-10-28T02:30:07Z | |
dc.date.available | 2014-10-28T02:30:07Z | |
dc.date.issued | 2000-07-28 | |
dc.identifier.citation | Dong, F.M.,Koh, K.M.,Teo, K.L.,Little, C.H.C.,Hendy, M.D. (2000-07-28). An attempt to classify bipartite graphs by chromatic polynomials. Discrete Mathematics 222 (1-3) : 73-88. ScholarBank@NUS Repository. | |
dc.identifier.issn | 0012365X | |
dc.identifier.uri | http://scholarbank.nus.edu.sg/handle/10635/102824 | |
dc.description.abstract | For integers p,q,s with p≥q≥3 and 1 ≤s≤q - 1, let script K sign-s(p,q) (resp. script K sign-s 2(p,q)) denote the set of connected (resp. 2-connected) bipartite graphs which can be obtained from Kp,q by deleting a set of s edges. In this paper, we first find an upper bound for the 3-independent partition number of a graph G ∈ script K sign-s(p,q) with respect to the maximum degree Δ(G′) of G′, where G′ = Kp,q - G. By using this result, we show that the set { G | G ∈ script K sign-s 2(p,q), Δ(G′) = i} is closed under the chromatic equivalence for every integer i with s≥i≥(s + 3)/2. From this result, we prove that for any G ∈ script K sign-s 2(p,q) with p≥q≥3, if 5≤s≤q - 1 and Δ(G′) = s - 1, or 7≤s≤q - 1 and Δ(G′) = s - 2, then G is chromatically unique. © 2000 Elsevier Science B.V. All rights reserved. | |
dc.source | Scopus | |
dc.subject | Bipartite graphs | |
dc.subject | Chromatic equivalence | |
dc.subject | Chromatic polynomials | |
dc.type | Article | |
dc.contributor.department | MATHEMATICS | |
dc.description.sourcetitle | Discrete Mathematics | |
dc.description.volume | 222 | |
dc.description.issue | 1-3 | |
dc.description.page | 73-88 | |
dc.description.coden | DSMHA | |
dc.identifier.isiut | NOT_IN_WOS | |
Appears in Collections: | Staff Publications |
Show simple item record
Files in This Item:
There are no files associated with this item.
Google ScholarTM
Check
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.