An attempt to classify bipartite graphs by chromatic polynomials

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.