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 shor...
| Main Author: | |
|---|---|
| Format: | Article |
| Published: |
Elsevier
1991
|
| Online Access: | http://psasir.upm.edu.my/id/eprint/114124/ |
| _version_ | 1848866411615617024 |
|---|---|
| author | Peng, Y.H. |
| author_facet | Peng, Y.H. |
| author_sort | Peng, Y.H. |
| building | UPM Institutional Repository |
| collection | Online Access |
| description | 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. |
| first_indexed | 2025-11-15T14:20:11Z |
| format | Article |
| id | upm-114124 |
| institution | Universiti Putra Malaysia |
| institution_category | Local University |
| last_indexed | 2025-11-15T14:20:11Z |
| publishDate | 1991 |
| publisher | Elsevier |
| recordtype | eprints |
| repository_type | Digital Repository |
| spelling | upm-1141242024-12-03T04:05:33Z http://psasir.upm.edu.my/id/eprint/114124/ On the chromatic uniqueness of certain bipartite graphs Peng, Y.H. 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. Elsevier 1991-11 Article PeerReviewed Peng, Y.H. (1991) On the chromatic uniqueness of certain bipartite graphs. Discrete Mathematics, 94 (2). pp. 129-140. ISSN 0012-365X; eISSN: 0012-365X https://linkinghub.elsevier.com/retrieve/pii/0012365X91903202 10.1016/0012-365x(91)90320-2 |
| spellingShingle | Peng, Y.H. On the chromatic uniqueness of certain bipartite graphs |
| title | On the chromatic uniqueness of certain bipartite graphs |
| title_full | On the chromatic uniqueness of certain bipartite graphs |
| title_fullStr | On the chromatic uniqueness of certain bipartite graphs |
| title_full_unstemmed | On the chromatic uniqueness of certain bipartite graphs |
| title_short | On the chromatic uniqueness of certain bipartite graphs |
| title_sort | on the chromatic uniqueness of certain bipartite graphs |
| url | http://psasir.upm.edu.my/id/eprint/114124/ http://psasir.upm.edu.my/id/eprint/114124/ http://psasir.upm.edu.my/id/eprint/114124/ |