# On Uniquely List Colorable Graphs11footnote 1 The research is partially supported by the Institute for Studies in Theoretical Physics and Mathematics (IPM), Tehran, Iran.

## 1 Introduction and preliminaries

We consider simple graphs which are finite, undirected, with no loops or multiple edges. For the necessary definitions and notation we refer the reader to standard texts, such as . In this section we mention some of the definitions and results which are referred to throughout the paper.

For each vertex $`v`$ in a graph $`G`$, let $`L(v)`$ denote a list of colors available for $`v`$. A list coloring from the 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. The idea of list colorings of graphs is due independently to V. G. Vizing  and to P. Erdös, A. L. Rubin, and H. Taylor . For a recent survey on list coloring we refer the interested reader to N. Alon . It is interesting to note that a list coloring of $`K_n`$ is nothing but a system of distinct representatives (SDR) for the collection $`=\{L(v)|vV(K_n)\}`$.

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 a uniquely $`k`$–list colorable graph or a U$`k`$LC graph for short.

###### Example

. The graph $`K_4e`$ is a uniquely $`2`$–list colorable graph.

In Figure 1 a collection of lists is given, each of size two, and it can easily be checked that there is a unique coloring with these lists.

###### Remark

.  It is clear from the definition of uniquely $`k`$–list colorable graphs that each U$`k`$LC graph is also a U$`(k1)`$LC graph.

The following theorem of Marshal Hall, which is a corollary of the celebrated Marriage Theorem of P. Hall and gives a lower bound for the number of SDRs, is a motivation for the definition of U$`k`$LC graphs.

###### Theorem A

.  If $`n`$ sets $`S_1,S_2,\mathrm{},S_n`$ have an SDR and the smallest of these sets contains $`k`$ objects, then if $`kn`$, there are at least $`k(k1)\mathrm{}(kn+1)`$ different SDRs; and if $`k<n`$, there are at least $`k!`$ different SDRs.

###### Corollary

. If the sets $`S_1,S_2,\mathrm{},S_n`$ have an SDR and the smallest of these sets is of size $`k`$ ( $`k>1`$), then they have at least two SDRs. Or equivalently, the complete graph $`K_n`$ is not U$`k`$LC.

If in the above corollary instead of $`K_n`$ we take any graph, then it is natural to ask the following question.

###### Question

. For which graphs does the result of the above corollary hold?

We say that a graph $`G`$ has the property $`M(k)`$ ($`M`$ for Marshal Hall) if and only if it is not uniquely $`k`$–list colorable. 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 at least two list colorings. Note that if one tries to relate the idea of uniqueness to list coloring, then he or she reaches this definition naturally.

M. Mahdian and E.S. Mahmoodian characterized uniquely $`2`$–list colorable graphs. They showed that,

###### Theorem B

.  A connected graph $`G`$ has the property $`M(2)`$ if and only if every block of $`G`$ is either a cycle, a complete graph, or a complete bipartite graph.

It seems that characterizing U$`k`$LC graphs for any $`k`$ is not that easy. Even the U$`3`$LC graphs seem to be difficult to characterize. For example it will be shown below that, while there are some complete tripartite graphs which have the property $`M(3)`$, the property does not hold for any complete tripartite graph.

The following definition was first given in .

###### Definition

. The m–number  of a graph $`G`$, denoted by $`\text{m}(G)`$, is defined to be the least integer $`k`$ such that $`G`$ has the property $`M(k)`$.

E. S. Mahmoodian and M. Mahdian in  have obtained some results on the m–number of planar graphs and introduced some upper bounds on $`\text{m}(G)`$.

It is obvious from the definition of a U$`k`$LC graph that the graph $`G`$ is U$`k`$LC if and only if $`k<\text{m}(G)`$. For example, one can easily see that the graph $`K_4e`$ has the property $`M(3)`$ and in the above example we saw that it is U$`2`$LC, so $`m(K_4e)=3`$.

The concept of U$`k`$LC graphs also arise naturally in finding defining sets of graphs. In a given graph $`G`$, a set of vertices $`S`$ with an assignment of colors is called a defining set of $`k`$–coloring, if there exists a unique extension of the colors of $`S`$ to a $`k`$–coloring of the vertices of $`G`$. For more information on defining sets see . As it is mentioned there, critical sets in latin squares are just the minimal defining sets of $`n`$–colorings of $`K_n\times K_n`$. A latin square is an $`n\times n`$ array from the numbers $`1,2,\mathrm{},n`$ such that each of these numbers occurs in each row and in each column exactly once. A critical set  in an $`n\times n`$ array is a set $`S`$ of entries, such that there exists a unique extension of $`S`$ to a latin square of size $`n`$ and no proper subset of $`S`$ has this property. For a survey on critical sets in latin squares see .

Each set of vertices $`SV(G)`$ with an assignment of colors induces a list of colors for each vertex in $`GS`$. So to find out if $`S`$ is a defining set or not, we need to know whether $`GS`$ is uniquely list colorable with those lists.

In this paper we state some results which are towards characterizing U$`k`$LC graphs. In Section 2 we introduce some results which are helpful in determining the m–number of some graphs. In Section 3 some theorems about complete multipartite graphs are discussed. In Section 4 we present some examples of U$`k`$LC graphs, and finally in the last section we pose some open problems.

## 2 Some general results

The following lemma is very useful throughout the paper.

###### Lemma 1

. For every graph $`G`$ we have $`\text{m}(G)|E(\overline{G})|+2`$.

###### Proof.

Proof is by induction on $`r=|E(\overline{G})|`$. In the case $`r=0`$, $`G`$ is a complete graph and by Theorem B it has the property $`M(2)`$. Assume that the statement is true for every graph $`H`$ with $`|E(\overline{H})|<r`$ and let $`G`$ be a graph whose complement has $`r`$ edges. Suppose that there are assigned some lists of colors $`L(w)`$ of size at least $`r+2`$ to the vertices of $`G`$ and $`G`$ has an $`L`$–coloring $`c`$. Let $`u`$ and $`v`$ be two nonadjacent vertices of $`G`$. To obtain another $`L`$–coloring for $`G`$, we consider two cases.

If $`c(u)c(v)`$, consider the graph $`G_1=G+uv`$. We have $`|E(\overline{G_1})|=r1`$, and by induction hypothesis $`\text{m}(G_1)r+1`$. So there exists another $`L`$–coloring for $`G_1`$ which is also legal for $`G`$ itself.

Now if $`c(u)=c(v)`$, consider the graph $`G_2=G\{w|c(w)=c(v)\}`$. If $`V(G_2)=\mathrm{}`$, then $`G`$ is a null graph and the statement is trivial. Otherwise we have $`|E(\overline{G_2})|<r`$, and by induction hypothesis $`\text{m}(G_2)r+1`$. Assign to each vertex $`w`$ of $`G_2`$ the list $`L^{}(w)=L(w)\{c(u)\}`$. Again $`c|_{V(G_2)}`$ is an $`L^{}`$–coloring for $`G_2`$ and since $`|L^{}(w)|r+1`$ for each $`wV(G_2)`$, there exists another $`L^{}`$–coloring for $`G_2`$ which can be extended to an $`L`$–coloring of $`G`$, different from $`c`$, by giving the color $`c(u)`$ to all the vertices of $`G`$ which are not in $`G_2`$. $`\mathrm{}`$

From the following theorem we can deduce a lower bound for the number of vertices in a U$`k`$LC graph.

###### Theorem 1

. If a graph $`G`$ has at most $`3k`$ vertices, then $`m(G)k+1`$.

###### Proof.

Proof is by induction on $`k`$. For $`k=1`$ the statement obviously holds. Suppose that $`k2`$, and $`G`$ is a graph with at most $`3k`$ vertices, and let there be lists of colors, each of size at least $`k+1`$, assigned to the vertices of $`G`$ and further suppose that there exists a list coloring $`c`$ for $`G`$, from these lists. We show that there exists another coloring for $`G`$ from these lists.

If one color class has at least three vertices, we can remove that class from $`G`$ and its color from the lists of remaining vertices, and by induction hypothesis a new coloring exists for the remaining graph which extends to all of $`G`$. So assume that each color class has at most two vertices. By adding new edges between all vertices with different colors in $`c`$, we obtain a graph whose complement is union of some $`K_1`$s and some $`K_2`$s. Denote the number of $`K_2`$s by $`r`$. If $`rk1`$, we obtain a new coloring by the lemma above, otherwise $`rk`$. Now if there exists a vertex $`v`$ whose list contains a color $`x`$ which is not used in the coloring $`c`$, then we can obtain a new coloring by changing the color of $`v`$ to $`x`$. Otherwise the union of all lists has exactly $`nr2k`$ elements. If $`u`$ and $`v`$ are two vertices such that $`c(u)=c(v)`$, then since the unused colors in the lists of $`u`$ and $`v`$ are chosen from a ($`2k1`$)–set, thus $`u`$ and $`v`$ must have a common unused color. Consider a $`K_{nr}`$ obtained by identifying all the vertices in each color class of $`c`$ to a vertex. The list of each vertex in this $`K_{nr}`$ is the intersection of the lists of the vertices in the corresponding color class. So each list of the vertices in $`K_{nr}`$ has at least $`2`$ elements, and there exists a coloring for it from these lists. Hence by the property $`M(2)`$ of $`K_{nr}`$ we obtain a new coloring on it, which gives a new coloring for $`G`$.  $`\mathrm{}`$

The following two corollaries are immediate from the theorem above. The first one gives an upper bound for the m–number of a graph and the second one introduces a lower bound for the number of vertices in a U$`k`$LC graph.

###### Corollary 1

. If a graph $`G`$ has $`n`$ vertices then $`m(G)n/3+1`$.

###### Corollary 2

. Every U$`k`$LC graph has at least $`3k2`$ vertices.

Corollary 2 implies that a necessary condition to have equality in Lemma 1 is $`|V(G)|3|E(\overline{G})|+1`$. In the following proposition we see that when the edges of $`\overline{G}`$ are independent this condition is also sufficient .

###### Proposition 1

. If $`F`$ is a set of $`r`$ independent edges in $`K_n`$ and $`n3r+1`$, then $`m(K_nF)=r+2`$.

###### Proof.

Suppose $`F=\{x_1y_1,\mathrm{},x_ry_r\}`$, and $`z_0,\mathrm{},z_s`$ are the vertices in $`K_nV(F)`$. By the hypothesis $`sr`$. Assign the list $`\{0,1,\mathrm{},r\}`$ to each $`x_i`$ and to $`z_0`$, and for each $`i1`$ assign the list $`\{r+1,\mathrm{},2r,i\}`$ to $`y_i`$, and the list $`\{1,\mathrm{},r,r+i\}`$ to $`z_i`$. Since the induced subgraph of $`K_nF`$ on $`\{x_1,\mathrm{},x_r,z_0\}`$ is a complete graph, all the colors $`0,1,\mathrm{},r`$ must appear on these vertices in any coloring of $`K_nF`$ from the assigned lists. So for each $`i1`$ the vertex $`z_i`$ must take the color $`r+i`$, and for each $`i1`$ $`y_i`$ receives the color $`i`$. Finally each $`x_i`$ must take the color $`i`$, and $`z_0`$ takes the color $`0`$.  $`\mathrm{}`$

## 3 Complete multipartite graphs

It is shown in  that any complete bipartite graph has the property $`M(2)`$. In the following theorem it is shown that one can not expect similar statement for complete tripartite graphs.

###### Theorem 2

. For each $`k2`$, there exists a complete tripartite U$`k`$LC graph.

###### Proof.

Let $`A=\{a_1,\mathrm{},a_{k1}\}`$, $`B=\{b_1,\mathrm{},b_{k1}\}`$, and $`C=\{c_1,\mathrm{},c_{k1}\}`$ be mutually disjoint sets. We denote all $`(k1)`$-subsets of $`BC`$ by $`\{A_1,\mathrm{},A_m\}`$, those of $`AC`$ by $`\{B_1,\mathrm{},B_m\}`$, and those of $`AB`$ by $`\{C_1,\mathrm{},C_m\}`$; where $`m=\left(\genfrac{}{}{0pt}{}{2k2}{k1}\right)`$.

Now consider a complete tripartite graph $`K_{m(k1),m(k1),m(k1)}`$ with the following list of colors on vertices in three parts, respectively: $`A_i\{a_j\}`$, $`B_i\{b_j\}`$, and $`C_i\{c_j\}`$; where $`i=1,2,\mathrm{},m`$ and $`j=1,2,\mathrm{},k1`$. We show that there is a unique coloring for this graph from the assigned lists.

First note that the union of all lists is $`ABC`$ which has $`3(k1)`$ elements. We show that in any coloring of this graph, there are at least $`k1`$ colors present on the vertices of each part. To show this, suppose to the contrary that there exists a coloring in which one part uses less than $`k1`$ colors. Without loss of generality let $`L`$ be the set of colors used to color the first part, and $`|L|<k1`$. Then $`(BC)L`$ has at least $`k`$ elements and $`AL`$ has at least one element. Now consider a set $`L^{}`$ which contains $`k1`$ elements from the set $`(BC)L`$ and an element from $`AL`$. Then $`LL^{}=\mathrm{}`$. But there is a vertex in the first part whose list is $`L^{}`$, a contradiction. So each part has at least $`k1`$ colors and since we have $`3(k1)`$ colors altogether, thus in any coloring each part has exactly $`k1`$ colors. It can be easily verified that the colors of each of the three parts must be $`A`$, $`B`$, and $`C`$, respectively. Therefore there is a unique coloring for $`K_{m(k1),m(k1),m(k1)}`$ from the assigned lists.  $`\mathrm{}`$

The following theorem and the propositions which follow are preparations to prove our main theorem of this section, Theorem 4, which is a characterization of uniquely $`3`$–list colorable complete multipartite graphs except for finitely many of them. The proof of the following useful lemma is immediate.

###### Lemma 2

. If $`L`$ is a $`k`$–list assignment to the vertices in the graph $`G`$, and $`G`$ has a unique $`L`$–coloring, then $`|_vL(v)|k+1`$ and all these colors are used in the (unique) $`L`$–coloring of $`G`$.

###### Theorem 3

. If $`G`$ is a complete multipartite graph which has an induced U$`k`$LC subgraph, then $`G`$ is U$`k`$LC.

###### Proof.

Let $`H`$ be an induced subgraph of $`G`$ which is U$`k`$LC. Assume that $`L`$ is a $`k`$–list assignment to the vertices in $`H`$, by which $`H`$ has a unique list coloring. For the vertices in $`G`$ we introduce lists of colors each of size $`k`$, such that $`G`$ is uniquely colorable by these lists. Assign the list $`L(v)`$ to each vertex $`v`$ in $`H`$. For each part of $`G`$ that contains some vertices in $`H`$, consider a vertex $`v`$ in $`H`$ in that part and assign the list $`L(v)`$ to all vertices in $`GV(H)`$ in that part. In any part of $`G`$ which does not contain any vertex in $`H`$, we assign a list $`A\{i\}`$, where $`A`$ is a set of $`k1`$ colors from the $`L`$–coloring of $`H`$ and $`i`$ is a new color.  $`\mathrm{}`$

We use the notation $`K_{sr}`$ for a complete $`r`$–partite graph in which each part is of size $`s`$. Notations such as $`K_{sr,t}`$, etc. are used similarly.

###### Proposition 2

. The graphs $`K_{3,3,3}`$, $`K_{2,4,4}`$, $`K_{2,3,5}`$, $`K_{2,2,9}`$, $`K_{1,2,2,2}`$, $`K_{1,1,2,3}`$, $`K_{1,1,1,2,2}`$, $`K_{14,6}`$, $`K_{15,5}`$, and $`K_{16,4}`$ are U$`3`$LC.

###### Proof.

First we show the truth of the statement for $`K_{1,1,2,3}`$ and $`K_{14,6}`$.

For $`K_{1,1,2,3}`$, let $`\{a\}`$, $`\{b\}`$, $`\{c,d\}`$, and $`\{e,g,f\}`$ be the parts in $`K_{1,1,2,3}`$. We assign the following lists for the vertices of this graph: $`L(a)=L(c)=L(f)=\{1,3,4\}`$, $`L(b)=L(d)=L(g)=\{2,3,4\}`$, and $`L(e)=\{1,2,4\}`$. A unique coloring exists from the assigned lists, because the vertices $`b`$, $`d`$ and $`g`$ form a triangle and all of them have the list $`\{2,3,4\}`$, thus the colors $`2`$, $`3`$, and $`4`$ all occur on these vertices. The vertex $`a`$ is adjacent to these three vertices, so it is forced to take the color $`1`$. Now the colors $`3`$, $`4`$ must both occur on $`c`$ and $`f`$ so $`b`$ must take the color $`2`$. Finally $`e`$ is forced to take the color $`4`$, $`c`$ and $`d`$ must take $`3`$, and the two remaining vertices $`f`$ and $`g`$ must take $`4`$.

For $`K_{14,6}`$, assign the lists $`\{1,5,6\}`$, $`\{2,5,6\}`$, $`\{3,5,6\}`$, and $`\{4,5,6\}`$ to the vertices in the parts which have one vertex each, and the lists $`\{1,2,5\}`$, $`\{1,3,5\}`$, $`\{1,4,6\}`$, $`\{2,3,6\}`$, $`\{2,4,6\}`$, $`\{3,4,5\}`$ to the vertices in the last part. In any coloring we need all six colors because the last part needs at least two colors. Now none of the colors $`1,2,3`$, and $`4`$ can appear on the last part because in that case we need more than two colors on the last part, a contradiction.

For each of the other eight graphs one can check by similar argument that it has a unique coloring from the lists given below:

$`K_{3,3,3}`$: $`\{\{\underset{¯}{\mathrm{𝟣}}\mathrm{𝟥𝟦},\underset{¯}{\mathrm{𝟣}}\mathrm{𝟥𝟧},\underset{¯}{\mathrm{𝟤}}\mathrm{𝟦𝟧}\},\{\mathrm{𝟣𝟤}\underset{¯}{\mathrm{𝟥}},\mathrm{𝟣}\underset{¯}{\mathrm{𝟦}}\mathrm{𝟧},\underset{¯}{\mathrm{𝟥}}\mathrm{𝟧𝟨}\},\{\mathrm{𝟣𝟥}\underset{¯}{\mathrm{𝟨}},\mathrm{𝟣𝟦}\underset{¯}{\mathrm{𝟧}},\mathrm{𝟤𝟥}\underset{¯}{\mathrm{𝟧}}\}\}`$   
$`K_{2,4,4}`$: $`\{\{\underset{¯}{\mathrm{𝟣}}\mathrm{𝟥𝟧},\underset{¯}{\mathrm{𝟤}}\mathrm{𝟦𝟨}\},\{\mathrm{𝟣}\underset{¯}{\mathrm{𝟥}}\mathrm{𝟧},\mathrm{𝟤}\underset{¯}{\mathrm{𝟦}}\mathrm{𝟨},\underset{¯}{\mathrm{𝟥}}\mathrm{𝟧𝟨},\underset{¯}{\mathrm{𝟦}}\mathrm{𝟧𝟨}\},\{\mathrm{𝟣𝟤}\underset{¯}{\mathrm{𝟧}},\mathrm{𝟥𝟦}\underset{¯}{\mathrm{𝟧}},\mathrm{𝟣𝟦}\underset{¯}{\mathrm{𝟨}},\mathrm{𝟤𝟥}\underset{¯}{\mathrm{𝟨}}\}\}`$   
$`K_{2,3,5}`$: $`\{\{\underset{¯}{\mathrm{𝟣}}\mathrm{𝟦𝟨},\underset{¯}{\mathrm{𝟤}}\mathrm{𝟥𝟧}\},\{\mathrm{𝟣}\underset{¯}{\mathrm{𝟥}}\mathrm{𝟨},\mathrm{𝟤}\underset{¯}{\mathrm{𝟥}}\mathrm{𝟧},\underset{¯}{\mathrm{𝟦}}\mathrm{𝟧𝟨}\},\{\mathrm{𝟣𝟤}\underset{¯}{\mathrm{𝟧}},\mathrm{𝟥𝟦}\underset{¯}{\mathrm{𝟧}},\mathrm{𝟣𝟥}\underset{¯}{\mathrm{𝟨}},\mathrm{𝟤𝟥}\underset{¯}{\mathrm{𝟨}},\mathrm{𝟤𝟦}\underset{¯}{\mathrm{𝟨}}\}\}`$   
$`K_{2,2,9}`$: $`\{\{\underset{¯}{\mathrm{𝟣}}\mathrm{𝟧𝟨},\underset{¯}{\mathrm{𝟤}}\mathrm{𝟥𝟦}\},\{\mathrm{𝟣}\underset{¯}{\mathrm{𝟥}}\mathrm{𝟧},\mathrm{𝟣}\underset{¯}{\mathrm{𝟦}}\mathrm{𝟨}\},\{\mathrm{𝟣𝟤}\underset{¯}{\mathrm{𝟧}},\mathrm{𝟣𝟥}\underset{¯}{\mathrm{𝟧}},\mathrm{𝟣𝟦}\underset{¯}{\mathrm{𝟧}},\mathrm{𝟣𝟤}\underset{¯}{\mathrm{𝟨}},\mathrm{𝟣𝟥}\underset{¯}{\mathrm{𝟨}},\mathrm{𝟣𝟦}\underset{¯}{\mathrm{𝟨}},\mathrm{𝟤𝟦}\underset{¯}{\mathrm{𝟧}},\mathrm{𝟥𝟦}\underset{¯}{\mathrm{𝟧}},\mathrm{𝟤𝟥}\underset{¯}{\mathrm{𝟨}}\}\}`$   
$`K_{1,2,2,2}`$: $`\{\{\underset{¯}{\mathrm{𝟣}}\mathrm{𝟤𝟥}\},\{\mathrm{𝟣}\underset{¯}{\mathrm{𝟤}}\mathrm{𝟥},\underset{¯}{\mathrm{𝟤}}\mathrm{𝟦𝟧}\},\{\mathrm{𝟣𝟤}\underset{¯}{\mathrm{𝟥}},\underset{¯}{\mathrm{𝟥}}\mathrm{𝟦𝟧}\},\{\mathrm{𝟣𝟤}\underset{¯}{\mathrm{𝟦}},\mathrm{𝟣𝟤}\underset{¯}{\mathrm{𝟧}}\}\}`$   
$`K_{1,1,1,2,2}`$: $`\{\{\underset{¯}{\mathrm{𝟣}}\mathrm{𝟦𝟧}\},\{\underset{¯}{\mathrm{𝟤}}\mathrm{𝟦𝟧}\},\{\underset{¯}{\mathrm{𝟥}}\mathrm{𝟦𝟧}\},\{\mathrm{𝟣𝟤}\underset{¯}{\mathrm{𝟦}},\mathrm{𝟥}\underset{¯}{\mathrm{𝟦}}\mathrm{𝟧}\},\{\mathrm{𝟣𝟤}\underset{¯}{\mathrm{𝟧}},\mathrm{𝟥𝟦}\underset{¯}{\mathrm{𝟧}}\}\}`$   
$`K_{15,5}`$: $`\{\{\underset{¯}{\mathrm{𝟣}}\mathrm{𝟨𝟩}\},\{\underset{¯}{\mathrm{𝟤}}\mathrm{𝟨𝟩}\},\{\underset{¯}{\mathrm{𝟥}}\mathrm{𝟨𝟩}\},\{\underset{¯}{\mathrm{𝟦}}\mathrm{𝟨𝟩}\},\{\underset{¯}{\mathrm{𝟧}}\mathrm{𝟨𝟩}\},\{\mathrm{𝟣𝟤}\underset{¯}{\mathrm{𝟨}},\mathrm{𝟥𝟦}\underset{¯}{\mathrm{𝟨}},\mathrm{𝟣𝟧}\underset{¯}{\mathrm{𝟨}},\mathrm{𝟤𝟧}\underset{¯}{\mathrm{𝟩}},\mathrm{𝟥𝟦}\underset{¯}{\mathrm{𝟩}}\}\}`$   
$`K_{16,4}`$: $`\{\{\underset{¯}{\mathrm{𝟣}}\mathrm{𝟩𝟪}\},\{\underset{¯}{\mathrm{𝟤}}\mathrm{𝟩𝟪}\},\{\underset{¯}{\mathrm{𝟥}}\mathrm{𝟩𝟪}\},\{\underset{¯}{\mathrm{𝟦}}\mathrm{𝟩𝟪}\},\{\underset{¯}{\mathrm{𝟧}}\mathrm{𝟩𝟪}\},\{\underset{¯}{\mathrm{𝟨}}\mathrm{𝟩𝟪}\},\{\mathrm{𝟣𝟤}\underset{¯}{\mathrm{𝟩}},\mathrm{𝟥𝟦}\underset{¯}{\mathrm{𝟩}},\mathrm{𝟣𝟤}\underset{¯}{\mathrm{𝟪}},\mathrm{𝟧𝟨}\underset{¯}{\mathrm{𝟪}}\}\}`$  $`\mathrm{}`$

###### Proposition 3

. $`m(K_{2,2,3})=m(K_{2,3,3})=3`$.

###### Proof.

By Theorem B the graph $`K_{2,2,3}`$ is a U$`2`$LC graph, so $`m(K_{2,2,3})3`$. We show that $`m(K_{2,2,3})=3`$. Suppose that there are assigned color lists, each of size at least $`3`$, to the vertices in $`K_{2,2,3}`$ and $`c`$ is a coloring from those lists. If all vertices in a part of $`K_{2,2,3}`$ have the same color in $`c`$, we can remove that color from the lists of the other two parts and by the property $`M(2)`$ of complete bipartite graphs we obtain a different coloring on those parts which is extendible to $`K_{2,2,3}`$. So suppose that at least two colors appear on each part. Add new edges between those nonadjacent vertices that take different colors in $`c`$, the resulting graph is a $`K_7`$ or $`K_7e`$, both of which have the property $`M(3)`$. So we obtain another coloring which is a legal coloring for $`K_{2,2,3}`$.

The second graph is checked by a computer program and it has the property $`M(3)`$, so by Theorem B its m–number is equal to 3.  $`\mathrm{}`$

###### Proposition 4

. Every complete tripartite graph $`K_{1,s,t}`$ has the property $`M(3)`$. Thus if $`\mathrm{max}\{s,t\}2`$, then $`m(K_{1,s,t})=3`$.

###### Proof.

The proof is immediate by a technique similar to one used in Proposition 3.  $`\mathrm{}`$

###### Proposition 5

. For each $`s2`$, $`m(K_{1,1,1,s})=3`$.

###### Proof.

Suppose for each $`vV(K_{1,1,1,s})`$ there is assigned a color list $`L(v)`$ of size $`3`$, and $`K_{1,1,1,s}`$ has an $`L`$–coloring $`c`$. If one of the vertices in $`K_{1,1,1,s}`$ has a color in its list which is not used in $`c`$, we obtain a new $`L`$–coloring for $`K_{1,1,1,s}`$ by simply putting that unused color on that vertex. So suppose that each color in $`_vL(v)`$ is used in the coloring.

Call the vertices in the first three parts $`x,y`$, and $`z`$, and the vertices in the last part $`w_1,\mathrm{},w_s`$. Suppose that the colors of $`x,y`$, and $`z`$ in the coloring are $`1,2`$, and $`3`$, respectively. So for each $`i`$, $`L(w_i)`$ contains $`c(w_i)`$ and two colors from $`1,2`$, and $`3`$.

If two of the vertices $`x,y,`$ and $`z`$, say $`x`$ and $`y`$ have some colors of the last part in their lists, $`c(w_p)L(x)`$ and $`c(w_q)L(y)`$ where $`c(w_p)c(w_q)`$, then we obtain a new coloring $`c^{}`$ for $`K_{1,1,1,s}`$ by putting $`c(w_p)`$ on $`x`$, $`c(w_q)`$ on $`y`$, $`c(z)`$ on $`z`$, and since for each $`i=1,2,\mathrm{},s`$, there exists $`c^{}(w_i)L(w_i)\{1,2\}`$, we change each $`c(w_i)`$ by this $`c^{}(w_i)`$. Otherwise, either there is at most one color of the last part in $`L(x)L(y)L(z)`$, or there is one of $`x,y,`$ and $`z`$, say $`x`$, whose list contains two colors from the last part, and two other have no color of the last part in their lists. In the former case we can obtain a new coloring for the triangle induced on $`x,y,`$ and $`z`$ from the lists $`L(v)\{1,2,3\}`$ on each $`v\{x,y,z\}`$, by the property $`M(2)`$ of $`K_3`$. In the latter case a new coloring can be obtained by replacing the colors of $`y`$ and $`z`$.

We showed that $`K_{1,1,1,s}`$ has the property $`M(3)`$, and so $`m(K_{1,1,1,s})3`$. On the other hand it has an induced $`K_{1,1,2}`$ subgraph which is a U$`2`$LC graph, and so we have $`m(K_{1,1,1,s})>2`$.  $`\mathrm{}`$

###### Proposition 6

. For every $`r2`$, we have $`m(K_{1r,3})=3`$.

###### Proof.

Suppose there are some lists of colors each of size $`3`$ assigned to the vertices of $`K_{1r,3}`$, which have a coloring. We consider two cases and in each case obtain a new coloring for $`K_{1r,3}`$ from these lists. First consider the case that all vertices in the last part take the same color in the given coloring. By removing this color from the lists of other vertices, they have a new coloring because the complete graphs have the property $`M(2)`$. So at least two colors appear on the vertices in last part. Add new edges between those vertices in the last part that have different colors. The resulting graph is either a complete graph or a complete graph with an edge removed, and we know that both of those graphs have the property $`M(3)`$. So a new coloring can be obtained from the lists for the new graph. This coloring is also valid for $`K_{1r,3}`$.  $`\mathrm{}`$

Now we state our main theorem of this section.

###### Theorem 4

. Let $`G`$ be a complete multipartite graph that is not $`K_{2,2,r}`$, for $`r=4,5,\mathrm{},8`$, $`K_{2,3,4}`$, $`K_{14,4}`$, $`K_{14,5}`$, or $`K_{15,4}`$ then $`G`$ is U$`3`$LC if and only if it has one of the graphs in Proposition 2 as an induced subgraph.

###### Proof.

If $`G`$ has one of the graphs of Proposition 2 as an induced subgraph, then it is U$`3`$LC by Theorem 3. So we prove the other side of the statement. Assume that $`G`$ is not one of the graphs mentioned in the statement and it does not have any graphs of Proposition 2 as an induced subgraph. We show that it is not U$`3`$LC. There are two cases to be considered.

(i) $`G=K_{1r,s}`$, for some $`r`$ and $`s`$. If $`r3`$ or $`s3`$, then by Proposition 5 and Proposition 6 it has the property $`M(3)`$. So assume $`r4`$ and $`s4`$. Since $`G`$ does not contain a $`K_{14,6}`$ we must have $`4s5`$. If $`s=5`$ we have $`r=4`$ which is exempted. If $`s=4`$ we have $`r=4`$ or 5, which are also exempted.

(ii) $`G`$ has at least two parts whose sizes are greater than 1. Since it does not contain a $`K_{1,1,1,2,2}`$, it is either 4–partite, tripartite, or bipartite.

If $`G`$ is bipartite, it is not U$`3`$LC, by Theorem B.

If $`G`$ is 4–partite, since it does not contain a $`K_{1,2,2,2}`$ or a $`K_{1,1,2,3}`$, it must be $`K_{1,1,2,2}`$ which is not U$`3`$LC by Theorem 1.

So assume that $`G=K_{r,s,t}`$ for some $`tsr`$. Since it does not contain a $`K_{3,3,3}`$ we have $`t2`$. If $`t=1`$ then it is not U$`3`$LC by Proposition 4.

If $`t=2`$, since it does not contain a $`K_{2,4,4}`$ we must have $`s3`$.

If $`s=2`$ then $`G`$ must be a $`K_{2,2,r}`$ with $`r8`$. But now, if $`r3`$ it is not U$`3`$LC by Proposition 3, and the cases of $`4r8`$ are exempted.

If $`s=3`$ then $`G=K_{2,3,r}`$ where $`r4`$. Then if $`r3`$ it is not U$`3`$LC, by Proposition 3, and for $`r=4`$ it is exempted.  $`\mathrm{}`$

## 4 Some examples of U$`k`$LC graphs

In this section we introduce some examples of U$`k`$LC graphs.

###### Example 1

. The graph $`K_{1k,2(k1)}`$ has m–number equal to $`k+1`$.

###### Proof.

This is the example given in  as a U$`k`$LC graph. It is a special case of graphs discussed in Proposition 1.  $`\mathrm{}`$

###### Example 2

. The graph $`K_{1,2(k1),k1}`$ has m–number $`k+1`$.

###### Proof.

From each of the first $`k`$ parts choose a vertex and assign to it the list $`\{1,\mathrm{},k\}`$. To the other vertex in $`i`$–th part ($`2ik`$) assign the list $`\{k+1,\mathrm{},2k1,i\}`$. Finally in the last part, assign the list $`\{1,\mathrm{},k1,k+j\}`$ to the $`j`$–th vertex in that part ($`1jk1`$). Since this graph has a subgraph $`K_k`$ which has the list $`\{1,\mathrm{},k\}`$ on each of its vertices, by a similar argument as in the proof of Proposition 2, a unique coloring from these lists for $`K_{1,2(k1),k1}`$ can be obtained.  $`\mathrm{}`$

###### Example 3

. The complete $`(k+1)`$–partite graph $`K_{1,1,2,\mathrm{},k}`$ is U$`k`$LC.

###### Proof.

We use the colors from the set $`A=\{1,2,\mathrm{},k+1\}`$. Assign the list $`A\{k\}`$ to the vertex in the first part, and in the $`(i+1)`$–th part ($`1ik`$) assign the list $`A\{kj+2\}`$ to the $`j`$–th vertex $`(1ji)`$. Since $`\chi (K_{1,1,2,\mathrm{},k})=k+1`$, we need $`k+1`$ colors to color this graph, so all of the colors must be used and in each part we must have exactly one color. Hence the vertices in the $`(k+1)`$–th part must all take the color $`1`$, the vertices in the $`k`$–th part must all take the color $`2`$, …, the single vertex in the second part must take the color $`k`$, and finally the single vertex in the first part is forced to take the color $`k+1`$.  $`\mathrm{}`$

###### Example 4

. The graph $`𝒰_k`$ constructed below has m–number $`k+1`$:

Let the set $`\{v_1,\mathrm{},v_{3k2}\}`$ be the set of vertices in $`𝒰_k`$. The edges in $`𝒰_k`$ are $`v_iv_j`$s $`(ij)`$ where:

* $`1i,jk`$,
* $`1ik`$ and $`k+1j2k1`$,
* $`k+1i2k1`$ and $`2kj3k2`$,
* $`1ik1`$ and $`2kj3ki1`$.

###### Proof.

Assign the list $`\{1,\mathrm{},k\}`$ to $`v_1,\mathrm{},v_k`$, the list $`\{1,\mathrm{},k1,i\}`$ to $`v_i`$ where $`k+1i2k1`$, and the list $`\{k+1,\mathrm{},2k1,i2k+1\}`$ to $`v_i`$ where $`2ki3k2`$. Again since there exists a $`K_k`$ in $`𝒰_k`$ induced on $`\{v_1,\mathrm{},v_k\}`$ and with a similar argument as in the proof of Proposition 2, a unique coloring from these lists for $`𝒰_k`$ is obtained.  $`\mathrm{}`$

###### Example 5

. The graph $`𝒯_k`$ constructed below is U$`k`$LC for each $`k2`$:

$$V(G)=\{a_1,\mathrm{},a_{k1},b_1,\mathrm{},b_k,c_1,\mathrm{},c_{k1},d_1,\mathrm{},d_{2k3}\},$$

and for edges,

* Make a $`K_{2k1}`$ on $`a_i`$s and $`b_i`$s,
* Join $`b_i`$s to $`c_i`$s and $`c_i`$s to $`d_i`$s,
* Join $`a_i`$ to $`d_j`$ for $`1ik1`$ and $`ijk1`$,
* Join $`b_i`$ to $`d_j`$ for $`3ik`$ and $`kjk+i3`$.

###### Proof.

Assign some lists to the vertices in $`𝒯_k`$ as follows: $`L(a_i)=\{1,\mathrm{},k\}`$, $`L(b_1)=\{k,\mathrm{},2k1\}`$, $`L(b_i)=\{i1,k+1,\mathrm{},2k1\}`$ for $`i>1`$, $`L(c_i)=\{k+1,\mathrm{},2k1,2k+i1\}`$, and $`L(d_i)=\{i+1,2k,\mathrm{},3k2\}`$. It is easy to check that $`𝒯_k`$ has a unique coloring from these lists.  $`\mathrm{}`$

## 5 Some open problems

The following problems arise naturally from the work.

###### Problem 1

. Verify the property $`M(3)`$ for the graphs exempted in Theorem 4, i.e. $`K_{2,2,r}`$ for $`r=4,5,\mathrm{},8`$, $`K_{2,3,4}`$, $`K_{14,4}`$, $`K_{14,5}`$, and $`K_{15,4}`$.

###### Problem 2

. Characterize all graphs with m–number $`3`$.

###### Problem 3

. What is the computational complexity of the property $`M(3)`$?

## Acknowledgement

We thank Bashir Sadjad who pointed out that in Lemma 1, the edges of $`\overline{G}`$ are not necessarily supposed to be independent.