Unique List Coloring Of Compiete Multipartite Graphs And K-subdivision Graphs

The coloring problem of graph is one of the hot issue of graph theory.Among them,the unique list coloring is an important branch of the graph coloring problem,which has attracted wide attention of scholars.In the study of UkLC colorable graph,when k=2,all U2LC graphs have been characterized;when k=3,the U3LC complete multipartite graphs have been completely characterized;when k=4,the researchers characterized U4LC complete k(k≥6)-partite graph.In addition,it has been proven that a few special graph classes have the property M(k).However,there is no research result on whether k-sub division graph is UkLC graph or has the property M(k).Based on this,it continues to study UkLC complete multipartite graph,k-subdivision graph and get the following results in this paper.Firstly,the characterization of the U5LC complete multipartite graph is researched.By using the method of permutation,combination and classification,all but finitely many complete k(k≥9)-partite graphs which have at least two parts whose sizes are greater than 1 and are uniquely 5-list colorable are characterized.At the same time,a series of complete k(k ≤ 8)-partite graphs has the property M(5)or U5LC graph are proved.Secondly,the m-number of the graph K1*r,3*(k-2)is analyzed.By constructing a col-oring list of graph K1*(k-1),2*(k-2),3,it is proved that K1*(k-1),2*(k-2),3 is UkLC graph when k≥3.Furthermore,by discussing the coloring of each part of the graph K1*r,3*(k-2),it is proved that K1*r,3*(k-2)has the property M(k),and m(K1*r,3*(k-2))=k is determined.Meanwhile,the unique list coloring of the graph K1,3,3,3 is discussed,and m(K1,3,3,3)＝4 is obtained.finally,the unique list colorable k-subdivision graph G1/k(k≥2)is completely charac-terized.By analyzing the structure and coloring of the k-subdivision graph,it is proved that the graph G1/k has the property M(3)and m(G1/2)≤3.And the m-number of G1/k is 2 if and only if each block of the graph G is a cycle.