# 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].

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