Some Conclusion on Uniquek-List Colorable Complete Multipartite Graphs

[摘要] If a graphGadmits ak-list assignmentLsuch thatGhas a uniqueL-coloring, thenGis called uniquelyk-list colorable graph, or UkLCgraph for short. In the process of characterizing UkLC graphs, the complete multipartite graphsK1*r,s(r,s∈N)are often researched. But it is usually not easy to construct the uniquek-list assignment ofK1*r,s. In this paper, we give some propositions about the property of the graphK1*r,swhen it is UkLC, which provide a very significant guide for constructing such list assignment. Then a special example of UkLC graphsK1*r,sas a application of these propositions is introduced. The conclusion will pave the way to characterize UkLCcomplete multipartite graphs.

[学科分类] 应用数学