Uniquely list colorability of complete tripartite graphs

Le Xuan Hung

Čebyševskij sbornik, Tome 23 (2022) no. 2, pp. 170-178

Résumé

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$.

Détail

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