Please use this identifier to cite or link to this item:

`http://scholarbank.nus.edu.sg/handle/10635/104100`

Title: | Sharp bounds for the number of 3-independent partitions and the chromaticity of bipartite graphs |

Authors: | Dong, F.M. Koh, K.M. Teo, K.L. Little, C.H.C. Hendy, M.D. |

Keywords: | Bipartite graphs Chromatic equivalence Chromatic polynomials Chromatic uniqueness |

Issue Date: | May-2001 |

Citation: | Dong, F.M.,Koh, K.M.,Teo, K.L.,Little, C.H.C.,Hendy, M.D. (2001-05). Sharp bounds for the number of 3-independent partitions and the chromaticity of bipartite graphs. Journal of Graph Theory 37 (1) : 48-77. ScholarBank@NUS Repository. |

Abstract: | Given a graph G and an integer k ≥ 1, let α(G,k) denote the number of k-independent partitions of G. Let K -S(p,q) (resp., K 2 -S(p,q)) denote the family of connected (resp., 2-connected) graphs which are obtained from the complete bipartite graph KpiQ by deleting a set of S edges, where p ≥ q ≥ 2. This paper first gives a sharp upper bound for α(G,3), where G ∈ K -S(p,q] and 0 ≤ S ≤ (p-1)(q-1) (resp., G ∈ K 2 -S(p,q) and 0 ≤ S ≤ p + q - 4). These bounds are then used to show that if G ∈ K -S(p,q) (resp., G ∈ K 2 -S (p,q)), then the chromatic equivalence class of G is a subset of the union of the sets K -Si(p + i,q - i) where max{-S/q-1, - p-q/2} ≤ i ≤ S/p-1 and S i = S - i(p - q + i) (resp., a subset of K 2 -S(p,q). where either 0 ≤ S ≤ q - 1, or S ≤ 2q - 3 and p ≥ q + 4). By applying these results, we show finally that any 2-connected graph obtained from K p,q by deleting a set of edges that forms a matching of size at most q - 1 or that induces a star is chromatically unique. © 2001 John Wiley & Sons, Inc. |

Source Title: | Journal of Graph Theory |

URI: | http://scholarbank.nus.edu.sg/handle/10635/104100 |

ISSN: | 03649024 |

Appears in Collections: | Staff Publications |

Show full item record

###### Files in This Item:

There are no files associated with this item.

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.