Discontinuity, Nonlinearity, and Complexity
Chromaticity of some Tripartite Graphs
Discontinuity, Nonlinearity, and Complexity 11(4) (2022) 645650  DOI:10.5890/DNC.2022.12.006
Jun Yin, Haixing Zhao, Xiujuan Ma, Yalan Li
School of Computer, Qinghai Normal University
Key Laboratory of Tibetan Information Processing and Machine Translation, Qinghai Province,
Key Laboratory of Tibetan Information Processing, Ministry of Education,
Xining, Qinghai, 810008, P.R. of China
Download Full Text PDF
Abstract
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]=\{HH\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)$ .
Acknowledgments
This research is supported by the Nature Science
Funds of China (Nos.11801296 and 11961055), by the Nature Science Foundation from Qinghai Province (No. 2017ZJ949Q).
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), 134143.


[3]  Chen, X. (1998), Some families of chromatically unique bipartite graphs, Discrete Math., 184, 245253.


[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 3independent partition and the chromaticity of bipartite graphs, J. Graph Theory 37, 4877.


[5]  Koh, K.M. and Teo, K.L. (1990), The search for chromatically unique graphs, Graphs and Combinatorics, 6, 259285.


[6]  Lau, G.C., Peng, Y.H., and Chu, H.H. (2011), Chromatic uniqueness of certain complete 4partite graphs, Ars Combinatoria, 99, 377382.


[7]  Peng, Y.H. (1991), Chromatic uniqueness of certain bipartite graphs, Discrete Math. 94, 129140.


[8]  Roslan, H. and Peng, Y.H. (2011), Chromaticity of bipartite graphs with seven edges deleted, Ars Combinatoria, 99, 257277.


[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, 8999.


[10]  Zhao, H.X. (2005), Chromaticity and Adjoint Polynomials of Graphs, University of Twente, Netherland.
