×

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