# Some Conclusion on Uniquek-List Colorable Complete Multipartite Graphs

Authors: Yanning Wang; Yanyan Wang; Xuguang Zhang
Journal: Journal of Applied Mathematics
 (2013)

---

## Abstract

If a graphG 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.


---

## Body

## 1. Introduction

In this section, some definitions and results about list colorings which are referred to throughout the paper are introduced. For the necessary definitions and notation, we refer the reader to standard texts, such as [1]. Following the paper [2], we use the notation Ks*r(r,s∈N, N is the set of natural numbers) for a complete r-partite graph in which each part is of size s. Notation such as Ks*r,t,(r,s,t∈N) is used similarly.The idea of list colorings of graphs is due, independently, to Vizing [3] and Erdős et al. [4]. For a graph G=(V,E) and each vertex v∈V(G), let L(v) denote a list of colors available for v. L={L(v)∣v∈V(G)} is said to be a list assignment of G. If |L(v)|=k for all v∈V(G), then L is called k-list assignment of G. For example, the numbers nearby the vertices in Figure 1 are 2-list assignment of the graph. A list coloring from a given collection of lists is a proper coloring c such that c(v) is chosen from L(v). We will refer to such a coloring as an L-coloring[5]. In Figure 1, the set of circled numbers makes a 2-list coloring of the graph.Figure 1
The list of graph.The list coloring model can be used in the channel assignment [6–8]. The fixed channel allocation scheme leads to low channel utilization across the whole channel. It requires a more effective channel assignment and management policy, which allows unused parts of channel to become available temporarily for other usages so that the scarcity of the channel can be largely mitigated [6]. It is a discrete optimization problem. A model for channel availability observed by the secondary users is introduced in [6]. We abstract each secondary network topology into a graph, where vertices represent wireless users such as wireless lines, WLANs, or cells, and edges represent interferences between vertices. In particular, if two vertices are connected by an edge in the graph, we assume that these two vertices cannot use the same spectrum simultaneously. In addition, we associate with each vertex a set, which represents the available spectra at this location. Due to the differences in the geographical location of each vertex, the sets of spectra of different nodes may be different. Then a list coloring model is constructed.The research of list coloring consists of two parts: the choosability and the unique list colorability. Some relations between uniquely list colorability and choosability of a graph are presented in [9]. In this paper, we research the unique list colorability of graph.The concept ofunique list coloring was introduced by Dinitz and Martin [10] and independently by Mahmoodian and Mahdian [11], which can be used to study defining set of k-coloring [12] and critical sets in Latin squares [13]. Let G be a graph with n vertices, and suppose that for each vertex v in G, there exists a list of k colors L(v), such that there exists a unique L-coloring for G; then G is called uniquely k-list colorable graph or a UkLCgraph for short. It is obvious that the set of circled numbers makes a 2-list coloring of the graph in Figure 2. For a graph G, it is said to have the propertyM(k) if and only if it is not uniquely k-list colorable graph. So 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 exist two list colorings. Note that the m-number of a graph G, denoted by m(G), is defined to be the least integer k such that G has the property M(k).Figure 2
The list coloring of graph.It is clear from the definition of uniquelyk-list colorable graphs that each UkLC graph is also a U(k-1)LC graph [14]. That is to say that, a graph which has the property M(k-1) also has the property M(k).Mahdian and Mahmoodian [5] characterized uniquely 2-list colorable graphs. They showed the following.Proposition 1 (see [5]).
A connected graph has the propertyM(2) if and only if every block of G is either a cycle, a complete graph, or a complete bipartite graph.In paper [15], it is showed that recognizing uniquely k-list colorable graphs is Σ2p-complete for every k≥3; then uniquely 3-list colorable graphs are unlikely to have a nice characterization. But Ghebleh and Mahmoodian [14] and He et al. [16–18] have characterized the U3LC complete multipartite graphs, and one has the following.Proposition 2 (see [14]).
The graphsK3,3,3, K2,4,4, K2,3,5, K2,2,9, K1,2,2,2, K1,1,2,3, K1,1,1,2,2, K1*4,6, K1*5,5, and K1*6,4 are U3LC.Proposition 3 (see [16]).
LetG be a complete multipartite graph; then G is U3LC if and only if it has one of the graphs in Proposition 2 as an induced subgraph.Wang et al. [19] have characterized U4LC complete multipartite graphs with at least 6 parts except for finitely many of them.In the process of characterizing UkLC complete multipartite graphs, it is often researched that the property M(k) of complete multipartite graphs has only one part whose size is more than one; that is, K1*r,s(r,s∈N). Paper [14] studied the property M(3) of graphs K1*r,3 and K1,1,1,r. The following was concluded.Proposition 4 (see [14]).
For everyr≥2, m(K1*r,3)=m(K1,1,1,r)=3.The propertyM(4) of graphs K1*r,5 and K1*5,r is researched in paper [19], and it is showed the following.Proposition 5 (see [19]).
For everyr≥1, K1*5,r and K1*r,5 have the property M(4), and if r≥5, then m(K1*5,r)=m(K1*r,5)=4.Conclusions above are generalized by Wang et al. [20] recently.Proposition 6 (see [20]).
For everyr≥1, k≥2, K1*r,(2k-3) has the property M(k).Proposition 7 (see [20]).
For everyr≥1, k≥2, K1*(2k-3),r has the property M(k).But there is no other conclusion about what are the maximal numbersr and s such that the graph K1*r,s is a UkLC graph for every k. Besides, the property of list assignment of UkLC graph K1*r,s is still unclear, and there is a lack of the necessary conditions for the UkLC graph K1*r,s. It seems that the larger k is, the more difficult the characterizing UkLC graphs are.In fact, if we want to proof that some graphK1*r,s is a UkLC graph, we must find a k-list assignment such that there exists a unique list coloring. In general it is not easy to construct such list assignment, and it usually requires a lot of skills. But if some properties of such graphs are known, the construction process perhaps will become easier. In addition, it is hoped that one can obtain some properties of UkLC graph K1*r,s for every k, not only for special k.In this paper the property of the graphK1*r,s is researched when it is a UkLC graph. The paper is organized as follows. In Section 2, we give some propositions about the property of the graph K1*r,s when it is a UkLC graph. According to these propositions, a special example of UkLC graphs K1*r,s is introduced in Section 3. In Section 4, we discuss the results and give an open problem. The conclusion will pave the way to characterize UkLC complete multipartite graphs.


## 2. Property of the UkLC Graph K1*r,s

In this section, we list some theorems about the property of the graphK1*r,s when it is UkLC, as it is conducive to construct the list assignment of UkLC complete multipartite graphs and characterize the UkLC graphs.Theorem 8.
For everyr≥1, if K1*r,s is a UkLC graph, then s≥2 (r,s∈N).Proof.
Ifs=1, K1*r,s=K1*(r+1) has the property M(2) by Proposition 1; so it is not a U2LC graph, nor a UkLC graph which is contradictory to the suppose.In view of these facts, it is supposed thats≥2 for a UkLC graph K1*r,s in the following.In the process of proving Theorem9, for convenience, the r+1 parts of K1*r,s are denoted by Vi={vi} for i=1,2,…,r and Vr+1={vr+1,vr+2,…,vr+s}. For the given k-list assignment L: L(vi)={ci,1,ci,2,…,ci,k}, i=1,2,…,r+s, there is a unique k-list color c: c(vi)=ci,1, i=1,2,…,r+s. Furthermore, one has Di={ci,1}, i=1,2,…,r; Di¯={ci,2,ci,3,…,ci,k}, i=1,2,…,r; Dr+1={cr+1,1,cr+2,1,…,cr+s,1}; Dr+1¯={cr+1,2,cr+1,3,…,cr+1,k,cr+2,2,cr+2,3,…,cr+2,k,…,cr+s,2,cr+s,3,…,cr+s,k}.Theorem 9.
Suppose thatr≥1, k≥3, and s≥3. Suppose that for some r, s, k, K1*r,s is a UkLC graph, and the unique k-list color c from the k-list assignment L is defined as above; then one has the following:(1)
ci,1≠cj,1, where 1≤i,j≤r and i≠j; ci,1≠cj,1, where 1≤i≤r, r+1≤j≤r+s;(2)
|Dr+1|≥2;(3)
|Dr+1|≤s-2;(4)
ci,1∉{cj,2,cj,3,…,cj,k}, i,j=r+1,r+2,…,r+s;(5)
|⋃i=1r+1Di|=|⋃i=1r+1Di¯| and Di¯⊆⋃j≠iDi, i,j=1,2,…,r+1;(6)
there must be ai (1≤i≤r) such that Di¯⊆Dr+1.Proof.
LetG=K1*r,s.(1)
From the definition of the UkLC graph, this conclusion is obvious.(2)
Suppose that|Dr+1|=1, which means that cr+1,1=cr+2,1=⋯=cr+s,1.Let H=G-Vr+1=K1*r. We introduce a (k-1)-list assignment L′ to H as follows. For every vertex v in H, if a∈L(v), then L′(v)=L(v)∖{cr+1,1}; otherwise L′(v)=L(v)∖{b} where b∈L(v) and b≠c(v). Since L induces a list coloring c for G, H has exactly a L′-coloring, namely, the restriction of c on H. H=K1*r has the property M(2) by Proposition 1; so it has the property M(k), and we can obtain a new L′-coloring of H. From the construction of L′, we know that the new L′-coloring can be extended to G. Thus, G has a new L-coloring which is different from c which is contradictory to the fact that c is the unique k-list color.(3)
We use the reduction to absurdity.
Case 1. One has |Dr+1|=s which means that cr+1,1,cr+2,1,…,cr+s,1 are pairwise different.
Adding new edges between any two vertices in{vr+1,vr+2,…,vr+s}, the resulting graph is G′=Kr+s. Note that c is also a proper L-coloring of G′, and G′ has the property M(2) by Proposition 1; hence G′ has the property M(k). So we can obtain another coloring of G′, which is also a legal L-coloring for G, which is contradictory to the fact that c is the unique k-list color.
Case 2. One has |Dr+1|=s-1 which means that in {vr+1,vr+2,…,vr+s} there are just two vertices assigned a common color, and the others are pairwise different.
Not loss of generality, we say thatcr+1,1=cr+2,1 and ck,1 are pairwise different for k=r+3,r+4,…,r+s. Adding new edges between any two vertices in {v1,v2,…,vr,vr+3,vr+4,…,vr+s}, the resulting graph is G′′=Kr+s-2. A (k-1)-list assignment L′ to G′′ is introduced as follows. For every vertex v in G′′, if cr+1,1∈L(v), then L′(v)=L(v)∖{cr+1,1}; otherwise L′(v)=L(v)∖{b} where b∈L(v) and b≠c(v). It is obvious that |L′(v)|=k-1 for every v∈V(G′′), and the restriction of c on G′′ is an L′-coloring of G′′. Obviously, G′′=K1*(r+s-2) has the property M(2) by the Proposition 1 and the property M(k-1). By the property M(k-1) of G′′, we can obtain a new L′-coloring c′ of G′′, which can be extended to G as follows. For every vertex v in G, if v∈V(G′′), then c′′(v)=c′(v); otherwise c′′(v)=c(v). From the construction of L′, it is obvious that c′′ is a new L-coloring of G which is contradictory to the fact that c is the unique k-list color.
In sum,|Dr+1|≤s-2.(4)
Ifi=j, then it is obvious that the conclusion is true. If i≠j, then we suppose that the conclusion is wrong, which means that there are two numbers i0 and j0 such that i0≠j0 and ci0,1∈{cj0,2,cj0,3,…,cj0,k}. It is clear that ci0,1≠cj0,1. Let c′(vj0)=ci0,1 and let c′(vk)=ck,1 for k=1,2,…,r+s but k≠j0. Obviously, c′ is a new L-coloring of G which is contradictory to the fact that c is the unique k-list color.(5)
Proof by contradiction. Suppose that|⋃i=1r+1Di|≠|⋃i=1r+1Di¯|, and there are i0 and j0 such that 1≤i0≤r+s, 2≤j0≤k and ci0,j0∉⋃i=1r+1Di. Let c′(vi0)=ci0,j0 and let c′(vk)=ck,1 for k=1,2,…,r+s but k≠i0. Obviously c′ is a new L-coloring of G which is contradictory to the fact that c is the unique k-list color. Then from (3) we know that Di¯⊆⋃j≠iDi, i,j=1,2,…,r+1.(6)
By contradiction. Suppose for everyi (1≤i≤r) that Di¯⊈Dr+1; then it is obtained that |Di¯∖Dr+1|≥1. So we get that |L(vi)∖Dr+1|≥2 for every 1≤i≤r. Let H=G-Vr+1=K1*r. We introduce a 2-list assignment L′ to H as follows. For every vertex vi in H, we obtain L′(vi) by randomly getting rid of k-2 elements from L(vi) such that L′(vi)∩Dr+1=Φ and |L′(vi)|=2, as can be done because |L(vi)∖Dr+1|≥2. Since L induces a list coloring c for G, H has exactly one L′-coloring, namely, the restriction of c on H. H=K1*r has the property M(2) by Proposition 1; so we can obtain a new L′-coloring of H. From the construction of L′, we know that the new L′-coloring can be extended to G. Thus, G has a new L-coloring which is different from c which is contradictory to the fact that c is the unique k-list color.


## 3. An Example of UkLC Graphs K1*r,s

According the property of UkLC graph in Theorem 9, we construct a list assignment of graph K1*r,s for special r and s and prove that the graph is a UkLC graph in this section.Theorem 10.
LetM=(k-1)(2k-2k-1) where k≥2, the graph K1*(2k-2),M is a UkLC graph.Proof.
For convenience, the (2k-1) parts of K1*(2k-2),M are denoted by Vi={vi} for i=1,2,…,2k-2 and V2k-1={u1,u2,…,uM}.
LetA={1,2,…,2k-2}. We denote all (k-1)-subsets of A by {A1,A2,…,Am}, where m=(2k-2k-1). Now consider K1*(2k-2),M with the following k-list of colors on vertices. For i=1,2,…,2k-2, L(vi)={i,2k-1,2k,…,3k-3}. For every t=1,2,…,m, j=1,2,…,k-1, L(u(j-1)*m+t)={j+2k-2}∪At.
For example, whenk=3, K1*(2k-2),M=K1*4,12, and the above mentioned k-list assignment L for K1*4,12 is as follows:
(1){{1_56},{2_56},{3_56},{4_56},l{5_12,5_13,5_14,5_23,5_24,5_34,6_12,6_13,6_14,6_23,6_24,6_34}}.
Note that the list assignmentL makes a total of 3k-3 colors. Since K1*(2k-2),M is a complete (2k-1)-partite graph, the last part V2k-1 can take k-1 colors at the most. From the construction of L, it is obtained obviously that {2k-1,2k,…,3k-3} is the unique choice for a k-list coloring from L. Then the Vi(1≤i≤2k-2) must take the color i. In the example above, the colors in the list coloring are marked by underlines. So a unique k-list coloring from L is made and K1*(2k-2),M is a UkLC graph.Notice that for everyr≥1, k≥2, K1*(2k-3),r has the property M(k) by Proposition 7. Now the graph K1*(2k-2),M in Theorem 10 is a UkLC graph; so it is wrong with the proposition “for every r≥1, k≥2, K1*(2k-2),r has the property M(k)”. Therefore, (2k-3) is the maximal numbers in Proposition 7.


## 4. Discussion and Some Open Problems

It is not easy to characterize UkLC complete multipartite for any k. In fact, it is a very tricky job to construct a k-list assignment such that there exists a unique list coloring. Theorem 9 provides a direction for constructing such list assignment of K1*r,s, and perhaps it makes construction easier for the researchers. Furthermore, Theorem 9 is true for every k(k≥2 and k∈N), and the conclusion is extensive.It must be noted that the conditions in Theorem9 are only necessary conditions of K1*r,s for UkLC graph, not sufficient conditions.Theorem10 can be regarded as a application of Theorem 9. And from Theorem 10, it is known that (2k-3) is exactly the maximal numbers in Proposition 7. But notice that the number M=(k-1)(2k-2k-1) is not the minimal number for every k in Proposition 7. For example, when k=3, M=12 and K1*4,12 is U3LC according to Theorem 10. In fact K1*4,6 is U3LC by Propositions 2 and 3; so M=12 is not the minimal number for k=3 in Proposition 7. Moreover, it is very likely that for different k the minimal number is different in Proposition 7.The following problem arises naturally from the work.Problem. For every k, characterize all minimum number s such that the graph K1*(2k-2),s is  a UkLC graph.



---

*Source: 380861-2013-10-08.xml*