On Uniquely List Colorable Complete Multipartite Graphs

Abstract

A graph $G$ is called $uniquelyk-listcolorable$, or $UkLC$ for short, if it admits a $k$-list assignment $L$ such that $G$ has a unique $L$-coloring. A graph $G$ is said to have the property $M(k)$ (M for Marshal Hall) if and only if it is not $UkLC$. In $1999$, M. Ghebleh and E.S. Mahmoodian characterized the $U3LC$ graphs for complete multipartite graphs except for nine graphs. At the same time, for the nine exempted graphs, they give an open problem: verify the property $M(3)$ for the graphs $K_{2,2,\dots ,2}$ for $r=4,5,\dots ,8$, $K_{2,3,4}$, $K_{1\ast 4,4}$, $K_{1\ast 4,4}$, and $K_{1\ast 5,4}$. Until now, except for $K_{1\ast 5,4}$, the other eight graphs have been showed to have the property $M(3)$ by W. He et al. In this paper, we show that graph $K_{1\ast 5,4}$ has the property $M(3)$, and as consequences, $K_{1\ast 4,4}$, $K_{2,2,4}$ have the property $M(3)$. Therefore the $U3LC$ complete multipartite graphs are completely characterized.