On Uniquely List Colorable Complete Multipartite Graphs

Abstract

A graph \(G\) is called \({uniquely\; k-list \;colorable}\), 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,\ldots,2}\) for \(r = 4,5,\ldots,8\), \(K_{2,3,4}\), \(K_{1*4,4}\), \(K_{1*4,4}\), and \(K_{1*5,4}\). Until now, except for \(K_{1*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*5,4}\) has the property \(M(3)\), and as consequences, \(K_{1*4,4}\), \(K_{2,2,4}\) have the property \(M(3)\). Therefore the \(U3LC\) complete multipartite graphs are completely characterized.