zbMATH — the first resource for mathematics

On uniquely list colorable complete multipartite graphs. (English) Zbl 1224.05188
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 M. 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,r}$$, for $$r=4,5,\dots ,8$$, $$K_{2,3,4}$$, $$K_{1*4,4}$$, $$K_{1*4,5}$$, and $$K_{1*5,4}$$. Until now, except for $$K_{1*5,4}$$, the other eight graphs have been shown to have the property $$M(3)$$ by W. He et al. In this paper, we show that the graph $$K_{1*5,4}$$ has the property $$M(3)$$ and as a consequence, $$K_{1*4,4}$$, $$K_{2,2,4}$$ have the property $$M(3)$$. Therefore, the U3LC complete multipartite graphs are completely characterized.

MSC:
 05C15 Coloring of graphs and hypergraphs 05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)