Chromatically Unique Bipartite Graphs with Certain 3-independent Partition Numbers

Abstract

For integers $p$, $q$, $s$ with $p\ge q\ge 2$ and $s\ge0$, let ${\cal K}_2^{-s}(p,q)$ denote the set of $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 graph $G\in{\cal K}_2^{-s}(p,q)$ with $p\ge q\ge3$ and $1\le s\le q-1$, if the number of 3-independent partitions of $G$ is $2^{p-1}+2^{q-1}+s+3$, then $G$ is chromatically unique. This result extends the similar theorem by Dong et al. (Discrete Math. vol. 224 (2000) 107--124). Keywords: Chromatic polynomial; chromatically equivalence; chromatically unique.