2007 | OriginalPaper | Chapter
Note on Characterization of Uniquely 3-List Colorable Complete Multipartite Graphs
Authors : Yongqiang Zhao, Wenjie He, Yufa Shen, Yanning Wang
Published in: Discrete Geometry, Combinatorics and Graph Theory
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
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.