On chromatic uniqueness of some complete tripartite graphs

Let $G=(V, E)$ be a graph with a vertex set $V$ and an edge set $E$. A coloring of a graph $G$ into $t$ colors is a map $\varphi \colon V\to \{1, 2, \ldots, t\}$, such that $\varphi(u) \neq \varphi(v)$ for any two adjacent vertices $u$ and $v$ of a graph $G$. We call numbers $1, 2, \ldots, t$ as colors. A graph is called $t$-colorable if there exists its coloring into $t$ colors. A minimum integer $t$, for which $G$ is $t$-colorable, is called the chromatic number of $G$ and denoted as $\chi(G)$.

The number of colorings of a graph $G$ into $t$ colors is denoted as $P(G, t)$. It is well known (see, for example, [1]) that the function $P(G, \lambda)$ is a polynomial of variable $\lambda$. Two graphs $G$ and $H$ are called chromatically equivalent if $P(G, \lambda) = P(H, \lambda).$ A graph $G$ is called chromatically unique, if for any graph $H$ graphs $G$ and $H$ are chromatically equivalent iff they are isomorphic.

Much attention of researches was drawn to the problem of chromatic uniqueness of complete multipartite graphs $K(n_1, n_2, \ldots, n_t)$.

We proved the following theorem.

Theorem. Complete tripartite graph $K(n_1, n_2, n_3)$ is chromatically unique if $n_1 \geqslant n_2 \geqslant n_3 \geqslant 2$ and $n_1 - n_3 \leqslant 5$.

Chromatic uniqueness of graph $K(n_1, n_2, n_3)$ when $n_1 \geqslant n_2 \geqslant n_3 \geqslant 2$ and $n_1 - n_3 \leqslant 4$ was proved in [2-4]. The main result of this work is the proof of the theorem in the case when $n_1-n_3=5$.

Список литературы

1. M. O. Asanov, V. A. Baransky, V. V. Rasin, Discrete mathematics: graphs, algorithms, matroids, Lan, Saint-Petersburg, 2010 (Russian)
2. V. A. Baransky, T. A. Koroleva, “Chromatic uniqueness of certain complete tripartite graphs”, Izv. Ural. Gos. Univ. Mat. Mekh. Inform., 74:12 (2010), 5–26 (Russian)
3. Т. А. Королева, “Хроматическая определяемость некоторых полных трехдольных графов. I”, Тр. ИММ УрО РАН, 13, № 3, 2007, 65–83    
4. T. A. Koroleva, “Chromatic uniqueness of some complete tripartite graphs. II”, Izv. Ural. Gos. Univ. Mat. Mekh. Inform., 74 (2010), 39–56 (Russian)