Chromaticity of some Tripartite Graphs
DOI:
https://doi.org/10.5890/DNC.2022.12.006Abstract
For any graph $G$, we use $P(G, \lambda)$ to denote the the chromatic polynomial of $G$. Two graphs $G$ and $H$ are said to be equivalent, simply denoted by $G\sim H$, if $P(G, \lambda)=P(H, \lambda)$. Let $[G]=\{H|H\sim G\}$. $G$ is said to be chromatically unique if $[G]=\{G\}$. Let $K(n, n, n)$ be the complete tripartite graph with each part vertex set having $n$ vertice and $S$ be an edge set of $s$ edges in $K(n, n, n)$. In this paper, we give some chromatically unique tripartite graphs obtained by deleting some edges from $K(n, n, n)$ .References
[1] Bondy, J.A. and Murty, U.S.R. (2008), Graph Theory, Springer.
[2] Chia, C.L. and Ho, C.K. (2009), Chromatic equivalence classes of complete tripartite graphs, Discrete Math., 309(1), 134-143.
[3] Chen, X. (1998), Some families of chromatically unique bipartite graphs, Discrete Math., 184, 245-253.
[4] Dong, F.M., Koh, K.M., Teo, K.L., Little, C.H.C., and Hendy, M.D. (2001), Sharp bounds for the number of 3-independent partition and the chromaticity of bipartite graphs, J. Graph Theory 37, 48-77.
[5] Koh, K.M. and Teo, K.L. (1990), The search for chromatically unique graphs, Graphs and Combinatorics, 6, 259-285.
[6] Lau, G.C., Peng, Y.H., and Chu, H.H. (2011), Chromatic uniqueness of certain complete 4-partite graphs, Ars Combinatoria, 99, 377-382.
[7] Peng, Y.H. (1991), Chromatic uniqueness of certain bipartite graphs, Discrete Math. 94, 129-140.
[8] Roslan, H. and Peng, Y.H. (2011), Chromaticity of bipartite graphs with seven edges deleted, Ars Combinatoria, 99, 257-277.
[9] Teo, C.P. and Koh, K.M. (1990), The chromaticity of complete bipartite graphs with at most one edge deleted, J. Graph Theory, 14, 89-99.
[10] Zhao, H.X. (2005), Chromaticity and Adjoint Polynomials of Graphs, University of Twente, Netherland.
Article Metrics
Usage tracking begins September 1, 2026.