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

✍ Scribed by F. M. Dong; K. M. Koh; K. L. Teo; C. H. C. Little; M. D. Hendy

• Publisher: John Wiley and Sons
• Year: 2001
• Tongue: English
• Weight: 233 KB
• Volume: 37
• Category: Article
• ISSN: 0364-9024
• DOI: 10.1002/jgt.1003

✦ Synopsis

Abstract

Given a graph G and an integer k ≥ 1, let α(G, k) denote the number of k‐independent partitions of G. Let 𝒦^−s^(p,q) (resp., 𝒦~2~^−s^(p,q)) denote the family of connected (resp., 2‐connected) graphs which are obtained from the complete bipartite graph K~p,q~ by deleting a set of s edges, where p ≥ q ≥ 2. This paper first gives a sharp upper bound for α(G,3), where G ∈ 𝒦 ^−s^(p,q) and 0 ≤ s ≤ (p − 1)(q − 1) (resp., G ∈ 𝒦 ~2~^−s^(p,q) and 0 ≤ s ≤ p + q − 4). These bounds are then used to show that if G ∈ 𝒦 ^−s^(p,q) (resp., G ∈ 𝒦 ~2~^−s^ (p,q)), then the chromatic equivalence class of G is a subset of the union of the sets 𝒦^−s^~i~(p+i,q−i) where max ${-{s\over q-1},-{p-q\over 2}}!\le ,i \le{s\over p-1}$ and s~i~ = s − i(p−q+i) (resp., a subset of 𝒦~2~^−s^(p,q), where either 0 ≤ s ≤ q − 1, or s ≤ 2__q__ − 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. J Graph Theory 37: 48–77, 2001