Chromatically Unique Bipartite Graphs with Certain 3-independent Partition Numbers II

Roslan H., and Peng, Y.H., (2006) Chromatically Unique Bipartite Graphs with Certain 3-independent Partition Numbers II. Bulletin of the Malaysian Mathematical Sciences Society, 29 (2). pp. 147-168. ISSN 0126-6705

Full text not available from this repository.

Official URL: http://math.usm.my/bulletin/pdf/v29n2/v29n2p6.pdf

Affiliations

Universiti Sains Malaysia, Pusat Pengajian Sains Matematik
Universiti Putra Malaysia, Jabatan Matematik and Institut Penyelidikan Matematik

Abstract

For integers $p, q, s$ with $p\geq q\geq 2$ and $s\geq 0$ , let $\mathcal{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 \mathcal{K}_{2}^{-s} (p,q)$ with $p\geq q\geq 3$ and $1\leq s\leq q - 1$ , if the number of $3-$ independent partitions of $G$ is $2^{p - 1} + 2^{q - 1} + s + 4$ , then $G$ is chromatically unique. This result extends the similar theorem by Dong et al. [Discrete Math. 224(2000) 107–124], and the result in [4].

2000 Mathematics Subject Classification: Primary 05C15