# zbMATH — the first resource for mathematics

On property $$M(3)$$ of some complete multipartite graphs. (English) Zbl 1097.05019
Let $$G$$ be a graph and suppose that for each vertex $$v$$ in $$G,$$ there exists a list $$L(v)$$ of $$k$$ colors such that there is a unique proper $$L$$-coloring $$c$$ for $$G$$ (that is, a unique proper vertex coloring $$c$$ where $$c(v)$$ is chosen from $$L(v)).$$ Then $$G$$ is called a uniquely $$k$$-list colorable graph. M. Ghebleh and E.S. Mahmoodian [Ars Comb. 59, 307–318 (2001; Zbl 1066.05063)] have characterized almost all uniquely $$3$$-list colorable complete multipartite graphs. In this paper, some remaining cases are studied, and it is proved that $$K_{1*4,5}$$, $$K_{1*4,4},$$ $$K_{2,2,r}$$ $$(r=4,5,6)$$ have property $$M(3).$$ This leads to an improvement of Ghebleh and Mahmoodian’s characterization. (Here a graph $$G$$ is said to have property $$M(k)$$ if and only if it is not uniquely $$k$$-list colorable. So $$G$$ has property $$M(k)$$ if for any collection of lists assigned to its vertices, each of size $$k$$, either there is no list coloring for $$G$$ or there exist at least two list colorings.)

##### MSC:
 05C15 Coloring of graphs and hypergraphs