Chromatic Uniqueness of Complete Bipartite Graphs With Certain Edges Deleted

Abstract

For integers \(p, q, s\) with \(p \geq q \geq 3\) and \(1 \leq s \leq q-1\), let \(\mathcal{K}^{-s}{p,q}\) (resp. \(\mathcal{K}_2^{-s}{p,q}\)) denote the set of connected (resp. 2-connected) bipartite graphs which can be obtained from \(K_{p,q}\) by deleting a set of \(s\) edges. In this paper, we prove that for any \(G \in \mathcal{K}_2^{-s}{p,q}\) with \(p \geq q \geq 3\), if \(9 \leq s \leq q-1\) and \(\Delta(G’) = s-3\) where \(G’ = K_{p,q} – G\), then \(G\) is chromatically unique.