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

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