On the chromatic uniqueness of certain bipartite graphs

Let K(p, q), p ≤ q, denote the complete bipartite graph in which the two partite sets consist of p and q vertices, respectively. We denote by K-r(p, q), the family of all graphs obtained by deleting any r distinct edges from K(p, q). Teo and Koh showed that K-1(p, q) is chromatically unique (in short χ-unique) for all p, q such that 3 ≤ p ≤ q. In this paper, we obtain a sufficient condition for a graph in K-2(p, q) to be χ-unique. Using this result, we then prove that each graph in K-2(p, p + d) is χ-unique for p ≥ 4and 0 ≤ d ≤ 3. For d ≥ 4, the graphs in K-2(p, q + d) are χ-unique if p > (A + √B)/4d2, where A and B are polynomials in d. We also show that each graph (≇K(4, 4) - K(1, 3)) in K-3(p, p + d) is χ-unique, for p ≥ 4 and d=0, 1; and all graphs in K-3(p, p + 2) are χ-unique if and only if all graphs in K-4(p + 1, p + 1) are χ-unique, where p ≥ 4. Finally we prove that every graph in K-4(p, p + 1) is χ-unique for p ≥ 5.

Actions (login required)

View Item