Some Conclusion on Unique k-List Colorable Complete Multipartite Graphs

Abstract EN

If a graph G admits a k-list assignment L such that G has a unique L-coloring, then G is called uniquely k-list colorable graph, or UkLC graph for short.

In the process of characterizing UkLC graphs, the complete multipartite graphs K1*r,s(r,s∈N) are often researched.

But it is usually not easy to construct the unique k-list assignment of K1*r,s.

In this paper, we give some propositions about the property of the graph K1*r,s when it is UkLC, which provide a very significant guide for constructing such list assignment.

Then a special example of UkLC graphs K1*r,s as a application of these propositions is introduced.

The conclusion will pave the way to characterize UkLC complete multipartite graphs.