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

05C15 Coloring of graphs and hypergraphs