zbMATH — the first resource for mathematics

On uniquely 4-list colorable complete multipartite graphs. (English) Zbl 1224.05194
Summary: A graph \(G\) is called uniquely \(k\)-list colourable, or UkLC for short, if it admits a \(k\)-list assignment \(L\) such that \(G\) has a unique \(L\)-colouring. 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 [Ars Comb. 51, 295–305 (1999; Zbl 0977.05046)] characterized the U2LC graphs, M. Ghebled and E. S. Mahmoodian [Ars Comb. 59, 307–318 (2001; Zbl 1066.05063)] characterized the U3LC graphs for complete multipartite graphs except for nine graphs in 2001. Recently, we [Y. Wang, Y. Shen, Y. Zhao and W. He, Ars Comb. 88, 367–377 (2008; Zbl 1224.05188)] verified that 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.

05C15 Coloring of graphs and hypergraphs
05C78 Graph labelling (graceful graphs, bandwidth, etc.)