RUS  ENG
Full version
JOURNALS // Ural Mathematical Journal // Archive

Ural Math. J., 2021 Volume 7, Issue 1, Pages 38–65 (Mi umj136)

On chromatic uniqueness of some complete tripartite graphs

Pavel A. Gein

Ural Federal University named after the First President of Russia B. N. Yeltsin, Ekaterinburg

Abstract: Let $P(G, x)$ be a chromatic polynomial of a graph $G$. Two graphs $G$ and $H$ are called chromatically equivalent iff $P(G, x) = H(G, x)$. A graph $G$ is called chromatically unique if $G\simeq H$ for every $H$ chromatically equivalent to $G$. In this paper, the chromatic uniqueness of complete tripartite graphs $K(n_1, n_2, n_3)$ is proved for $n_1 \geqslant n_2 \geqslant n_3 \geqslant 2$ and $n_1 - n_3 \leqslant 5$.

Keywords: chromatic uniqueness, chromatic equivalence, complete multipartite graphs, chromatic polynomial.

Language: English

DOI: 10.15826/umj.2021.1.004



Bibliographic databases:


© Steklov Math. Inst. of RAS, 2025