Chromatic equivalence classes of complete tripartite graphs
Some necessary conditions on a graph which has the same chromatic polynomial as the complete tripartite graph Km, n, r are developed. Using these, we obtain the chromatic equivalence classes for Km, n, n (where 1 ? m ? n) and Km1, m2, m3 (where | mi - mj | ? 3). In particular, it is shown that (i) K...
Saved in:
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Published: |
2023
|
| Subjects: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Summary: | Some necessary conditions on a graph which has the same chromatic polynomial as the complete tripartite graph Km, n, r are developed. Using these, we obtain the chromatic equivalence classes for Km, n, n (where 1 ? m ? n) and Km1, m2, m3 (where | mi - mj | ? 3). In particular, it is shown that (i) Km, n, n (where 2 ? m ? n) and (ii) Km1, m2, m3 (where | mi - mj | ? 3, 2 ? mi, i = 1, 2, 3) are uniquely determined by their chromatic polynomials. The result (i), proved earlier by Liu et�al. [R.Y. Liu, H.X. Zhao, C.Y. Ye, A complete solution to a conjecture on chromatic uniqueness of complete tripartite graphs, Discrete Math. 289 (2004) 175-179], answers a conjecture (raised in [G.L. Chia, B.H. Goh, K.M. Koh, The chromaticity of some families of complete tripartite graphs (In Honour of Prof. Roberto W. Frucht), Sci. Ser. A (1988) 27-37 (special issue)]) in the affirmative, while result (ii) extends a result of Zou�[H.W. Zou, On the chromatic uniqueness of complete tripartite graphs Kn1, n2, n3 J. Systems Sci. Math. Sci. 20 (2000) 181-186]. � 2008 Elsevier B.V. All rights reserved. |
|---|