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

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.