On Uniquely \(4\)-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\). The \(m\)-number of a graph \(G\), denoted by \(m(G)\), is defined to be the least integer \(k\) such that \(G\) has the property \(M(k)\). After M. Mahdian and E.S. Mahmoodian characterized the \(U2LC\) graphs, M. Ghebleh and E.S. Mahmoodian characterized the \(U3LC\) graphs for complete multipartite graphs except for nine graphs in 2001. Recently, W. He et al. verified all the nine graphs are not \(U3LC\) graphs. Namely, the \(U3LC\) complete multipartite graphs are completely characterized. In this paper, complete multipartite graphs whose \(m\)-number are equal to \(4\) are researched and the \(U4LC\) complete multipartite graphs, which have at least \(6\) parts, are characterized except for finitely many of them. At the same time, we give some results about some complete multipartite graphs whose number of parts is smaller than \(6\).