---

Discontinuity, Nonlinearity, and Complexity 11(4) (2022) 645--650 | 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]=\{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)$ .

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. 2017-ZJ-949Q).

References

1. [1]	Bondy, J.A. and Murty, U.S.R. (2008), Graph Theory, Springer.

2. [2]	Chia, C.L. and Ho, C.K. (2009), Chromatic equivalence classes of complete tripartite graphs, Discrete Math., 309(1), 134-143.

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

4. [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. [5]	Koh, K.M. and Teo, K.L. (1990), The search for chromatically unique graphs, Graphs and Combinatorics, 6, 259-285.

6. [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. [7]	Peng, Y.H. (1991), Chromatic uniqueness of certain bipartite graphs, Discrete Math. 94, 129-140.

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

9. [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. [10]	Zhao, H.X. (2005), Chromaticity and Adjoint Polynomials of Graphs, University of Twente, Netherland.