RUS  ENG
Full version
JOURNALS // Chebyshevskii Sbornik // Archive

Chebyshevskii Sb., 2022 Volume 23, Issue 2, Pages 170–178 (Mi cheb1184)

This article is cited in 2 papers

Uniquely list colorability of complete tripartite graphs

Le Xuan Hung

Hanoi University for Natural Resources and Environment (Hanoi, Vietnam)

Abstract: Given a list $L(v)$ for each vertex $v$, we say that the graph $G$ is $L$-colorable if there is a proper vertex coloring of $G$ where each vertex $v$ takes its color from $L(v)$. The graph is uniquely $k$-list colorable if there is a list assignment $L$ such that $|L(v)| = k$ for every vertex $v$ and the graph has exactly one $L$-coloring with these lists. If a graph $G$ is not uniquely $k$-list colorable, we also say that $G$ has property $M(k)$. The least integer $k$ such that $G$ has the property $M(k)$ is called the $m$-number of $G$, denoted by $m(G)$. In this paper, first we characterize about the property of the complete tripartite graphs when it is uniquely $k$-list colorable graphs, finally we shall prove that $m(K_{2,2,m})=m(K_{2,3,n})=m(K_{2,4,p})=m(K_{3,3,3})=4$ for every $m\ge 9,n\ge 5, p\ge 4$.

Keywords: Vertex coloring (coloring), list coloring, uniquely list colorable graph, complete $r$-partite graph.

UDC: 517.518.5

Received: 12.11.2021
Accepted: 22.06.2022

Language: English

DOI: 10.22405/2226-8383-2022-23-2-170-178



© Steklov Math. Inst. of RAS, 2025