Sharp bounds for the number of 3-independent partitions and the chromaticity of bipartite graphs

Given a graph G and an integer k greater than or equal to 1, let alpha (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 wh ich are obtained from the complete bipartite graph K-p,K-q by deleting a se t of s edges, where p greater than or equal to q greater than or equal to 2 . This paper first gives a sharp upper bound for alpha (G,3), where G is an element of K-s(p,q) and 0 less than or equal to s less than or equal to (p -1)(q-1) (resp., G is an element of K-2(-s)(p,q) and 0 less than or equal t o s less than or equal to p + q - 4). These bounds are then used to show th at if G is an element of K-S(p, 4) (resp., G is an element of K-2(-s) (p,q) ), then the chromatic equivalence class of G is a subset of the union of th e sets K-Si(p + i,q - i) where max {- s/q-1, - p-q/2} less than or equal to i less than or equal to s/p-1 and s(i)=s-i(p-q+i) (resp., a subset of K-2( -s)(p,q), where either 0 less than or equal to s less than or equal to q - 1, or s less than or equal to 2q - 3 and p greater than or equal to q + 4). By applying these results, we show finally that any 2-connected graph obta ined from K-p,K-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. (C) 2001 John W iley & Sons, Inc.