zbMATH — the first resource for mathematics

Note on characterization of uniquely 3-list colorable complete multipartite graphs. (English) Zbl 1149.05312
Akiyama, Jin (ed.) et al., Discrete geometry, combinatorics and graph theory. 7th China-Japan conference, CJCDGCGT 2005, Tianjin, China, November 18–20, 2005, Xi’an, China, November 22–24, 2005. Revised selected papers. Berlin: Springer (ISBN 978-3-540-70665-6/pbk). Lecture Notes in Computer Science 4381, 278-287 (2007).
Summary: Let \(G\) be a graph and suppose that for each vertex \(v\) of \(G\), there exists a list of \(k\) colors, \(L(v)\), such that there is a unique proper coloring for \(G\) from this collection of lists, then \(G\) is called a uniquely k-list colorable graph. M. Ghebleh and E. S. Mahmoodian characterized uniquely 3-list colorable complete multipartite graphs except for nine graphs. Recently, except for graph \(K_{2,3,4}\), the other eight graphs were shown not to be uniquely 3-list colorable by W. He and Y. Shen, etc. In this paper, it is proved that \(K_{2,3,4}\) is not uniquely 3-list colorable, and then the uniquely 3-list colorable complete multipartite graphs are characterized completely.
For the entire collection see [Zbl 1115.68001].

05C15 Coloring of graphs and hypergraphs
Full Text: DOI