Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
10331892 | Information Processing Letters | 2015 | 9 Pages |
Abstract
The property M(k) is a concept associated with the unique list coloring. A graph G has the 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 are at least two k-list colorings. The existing research results indicate that K1,1,1,r and K1âr,3 have the property M(3), and in addition K1â5,r and K1âr,5 have the property M(4) for every râ¥2. The results above are extended to every k in this paper. We will show that for every râ¥1, kâ¥2, K1âr,(2kâ3) and K1â(2kâ3),r have the property M(k). The conclusion will pave the way to characterizing unique k-list colorable complete multipartite graphs.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Yanning Wang, Yanyan Wang, Xuguang Zhang,