Please use this identifier to cite or link to this item:
Title: Sharp bounds for the number of 3-independent partitions and the chromaticity of bipartite graphs
Authors: Dong, F.M.
Koh, K.M. 
Teo, K.L.
Little, C.H.C.
Hendy, M.D.
Keywords: Bipartite graphs
Chromatic equivalence
Chromatic polynomials
Chromatic uniqueness
Issue Date: May-2001
Citation: Dong, F.M.,Koh, K.M.,Teo, K.L.,Little, C.H.C.,Hendy, M.D. (2001-05). Sharp bounds for the number of 3-independent partitions and the chromaticity of bipartite graphs. Journal of Graph Theory 37 (1) : 48-77. ScholarBank@NUS Repository.
Abstract: Given a graph G and an integer k ≥ 1, let α(G,k) denote the number of k-independent partitions of G. Let K -S(p,q) (resp., K 2 -S(p,q)) denote the family of connected (resp., 2-connected) graphs which are obtained from the complete bipartite graph KpiQ by deleting a set of S edges, where p ≥ q ≥ 2. This paper first gives a sharp upper bound for α(G,3), where G ∈ K -S(p,q] and 0 ≤ S ≤ (p-1)(q-1) (resp., G ∈ K 2 -S(p,q) and 0 ≤ S ≤ p + q - 4). These bounds are then used to show that if G ∈ K -S(p,q) (resp., G ∈ K 2 -S (p,q)), then the chromatic equivalence class of G is a subset of the union of the sets K -Si(p + i,q - i) where max{-S/q-1, - p-q/2} ≤ i ≤ S/p-1 and S i = S - i(p - q + i) (resp., a subset of K 2 -S(p,q). where either 0 ≤ S ≤ q - 1, or S ≤ 2q - 3 and p ≥ q + 4). By applying these results, we show finally that any 2-connected graph obtained from K p,q by deleting a set of edges that forms a matching of size at most q - 1 or that induces a star is chromatically unique. © 2001 John Wiley & Sons, Inc.
Source Title: Journal of Graph Theory
ISSN: 03649024
Appears in Collections:Staff Publications

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

Page view(s)

checked on Oct 26, 2018

Google ScholarTM


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