1 Introduction
A proper coloring of a graph G is a mapping
$\phi :V(G) \rightarrow \mathbb {N}$
such that
$\phi (u) \neq \phi (v)$
for every edge
$uv$
of
$E(G)$
. A k-coloring of G is a proper coloring of G using colors from
$[k] = \{1,2,\ldots , k\}$
. We say G is k-colorable if there is a k-coloring of G. The chromatic number
$\chi (G)$
of G is the minimum k such that G is k-colorable.
List coloring is a natural generalization of classical graph coloring, introduced independently by Erdős–Rubin–Taylor [Reference Erdős, Rubin and Taylor4] and Vizing [Reference Vizing24] in 1970s. A list assignment of G is a mapping L which assigns to each vertex v a set
$L(v)$
of permissible colors. An L-coloring of G is a proper coloring
$\phi $
of G with
$\phi (v) \in L(v)$
for each vertex v. We say that G is L-colorable if there exists an L-coloring of G, and G is k-choosable if G is L-colorable for any list assignment L of G with
$|L(v)| \ge k$
for each vertex v. More generally, for a function
$g: V(G) \to \mathbb {N}$
, we say G is g-choosable if G is L-colorable for every list assignment L with
$|L(v)| \ge g(v)$
for all
$v \in V(G)$
. The choice number
$\mathrm {ch}(G)$
of G is the minimum k for which G is k-choosable.
A k-coloring of a graph G is a special case of list coloring, where each vertex v has the same list
$L(v)=\{1,2,\ldots , k\}$
. So k-choosable implies k-colorable. At first glance, one might expect the reverse inequality to hold as well. The smaller intersection between lists would make it easier to assign distinct colors to adjacent vertices. However, the reverse inequality is far from true. It was observed in [Reference Erdős, Rubin and Taylor4] and [Reference Vizing24] that for any integer k, there are bipartite graphs that are not k-choosable. So the difference
$ch(G)-\chi (G)$
can be arbitrarily large.
A graph G is called chromatic-choosable if
$\chi (G)=ch(G)$
. Chromatic-choosable graphs have been studied a lot in the literature, and are related to some other difficult problems. For example, the famous Dinitz problem (see e.g., [Reference Zeilberger25]) asks the following question:
Given an
$n \times n$
array of n-sets, is it always possible to choose one from each set, keeping the chosen elements distinct in every row, and distinct in every column?
This problem can be equivalently stated as whether the line graph of
$K_{n,n}$
is chromatic-choosable? This problem was solved by Galvin [Reference Galvin5], who proved a more general result: the line graph of any bipartite multigraph is chromatic-choosable. On the other hand, Galvin’s result is a special case of a more general conjecture—the list coloring conjecture: line graphs of all multigraphs are chromatic-choosable. The list coloring conjecture was posed independently by many different researchers: Albertson and Collins, Bollobás and Harris, Gupta, and Vizing (see [Reference Bollobás and Harris1, Reference Häggkvist and Chetwynd7, Reference Jensen and Toft10]). It has attracted a lot of attention and remains open in general.
Ohba conjecture is another well-known conjecture about chromatic-choosable graphs. It was proved in [Reference Ohba18] that for any graph G,
$ch(G \vee K_n) = \chi (G \vee K_n)$
for sufficiently large n, where
$G \vee H$
is the join of G and H, i.e., the graph obtained from the disjoint union of G and H by adding edges connecting every vertex of G to every vertex of H. This means that graphs G with
$|V(G)|$
“close” to
$\chi (G)$
are chromatic-choosable. A natural problem is how close should be
$|V(G)|$
and
$\chi (G)$
to ensure that G be chromatic-choosable. Equivalently, what is the minimum number of vertices in a non-k-choosable k-chromatic graph?
We denote by
$K_{k_1\star n_1,k_2 \star n_2, \ldots , k_q \star n_q}$
the complete multi-partite graph with
$n_i$
parts of size
$k_i$
, for
$i=1,2,\ldots , q$
. If
$n_j=1$
, then the number
$n_j$
is omitted from the notation. It was proved in [Reference Enomoto, Ohba, Ota and Sakamoto3] that if k is an even integer, then
$K_{4, 2 \star (k-1)}$
and
$K_{3 \star (k/2+1), 1 \star (k/2-1)}$
are not k-choosable. These two graphs are k-chromatic graphs with
$2k+2$
vertices. Ohba [Reference Ohba18] conjectured that for any positive integer k, k-chromatic graphs with at most
$2k+1$
vertices are k-choosable. This conjecture has attracted considerable attention, and many partial results were proved before it was finally confirmed by Noel, Reed and Wu [Reference Noel, Reed and Wu17].
One approach has been to prove variants of Ohba’s conjecture in which
$|V(G)| \le 2k+1$
is replaced by
$|V(G)| \le \Phi (\chi (G))$
for some function
$\Phi $
with
$\Phi (k) < 2k+1$
. Ohba [Reference Ohba18] proved such a variant with
$\Phi (k)=k+\sqrt {k}$
, and Reed and Sudakov [Reference Reed and Sudakov21] improved the result to
$\Phi (k)= \frac 53 k - \frac 43$
. By using a sophisticated probabilistic method, Reed and Sudakov [Reference Reed and Sudakov20] proved that Ohba’s conjecture is asymptotically true: if
$|V(G)| \le (2-o(1))\chi (G)$
, then G is chromatic-choosable.
Another approach has been to show the conjecture holds for special families of graphs. He, Li, Shen, and Zheng [Reference Shen, He, Zheng and Li22] proved Ohba’s conjecture for graphs G with independence number
$\alpha (G) \le 3$
, by extending a result of Ohba [Reference Ohba19] who proved that if
$|V(G)| \le 2\chi (G)$
and
$\alpha (G) \le 3$
, then G is chromatic-choosable. Kostochka, Stiebitz, and Woodall [Reference Kostochka, Stiebitz and Woodall13] improved this result and showed that Ohba conjecture holds for graphs G with
$\alpha (G) \le 5$
. Also Ohba’s conjecture were verified for some particular complete multipartite graphs in [Reference He, Zhang, Cranston, Shen and Zheng9, Reference Shen, He, Zheng and Li22, Reference Shen, He, Zheng, Wang and Zhang23].
In 2015, Ohba’s conjecture was finally confirmed by Noel, Reed, and Wu [Reference Noel, Reed and Wu17].
Theorem 1.1 (Noel–Reed–Wu Theorem)
Every k-colorable graph with at most
$2k+1$
vertices is k-choosable.
Nevertheless, this is not the end of the story. More problems related to Ohba’s conjecture are posed and studied. One problem is what would be the choice number of k-chromatic graphs G with
$|V(G)|$
slightly bigger than
$2k+1$
. This question was addressed in [Reference Noel, West, Wu and Zhu16]. Another related problem is the online version of Ohba’s conjecture, which was posed in [Reference Huang, Wong and Zhu8], and has been studied in a few papers [Reference Chang, Chen, Guo and Huang2, Reference Kim, Kwon, Liu and Zhu12, Reference Kozik, Micek and Zhu14]. Some partial cases are verified and the conjecture remains open in general.
This paper explores the tightness of Ohba’s conjecture. Although Ohba’s conjecture is tight,
$K_{4, 2\star (k-1)}$
and
$K_{3 \star (k/2+1), 1 \star (k/2-1)}$
for even k are the only known k-chormatic graphs with
$2k+2$
vertices that are not k-choosable. In particular, Ohba’s conjecture was not known to be tight for odd integer k.
Noel [Reference Noel15] conjectured if k is odd, then all k-chromatic graphs with
$2k+2$
vertices are k-choosable.
Observe that for a k-chromatic graph G, by adding edges between vertices of distinct color classes, the resulting graph has the same chromatic number, and whose choice number is not decreased. Therefore in the study of minimum non-chromatic choosable graphs, it suffices to consider complete multipartite graphs.
The main result of this paper is that
$K_{4, 2\star (k-1)}$
and
$K_{3 \star (k/2+1), 1 \star (k/2-1)}$
for even k are the only non-k-choosable complete k-partite graphs with
$2k+2$
vertices.
Theorem 1.2 Assume
$G=(V,E)$
is a complete k-partite graph with
$|V| \le 2k+2$
, and
$G \ne K_{4, 2\star (k-1)}, K_{3\star (k/2+1), 1 \star (k/2 -1)}$
when k is even, and L is a k-list assignment of G. Then G is L-colorable.
As a consequence, Noel’s conjecture is confirmed.
Corollary 1.3 If k is odd, then every k-chromatic graph with at most
$2k+2$
vertices is chromatic-choosable.
For a positive integer k, let
For an odd integer k, it can be checked that
$K_{5,2\star (k-1)}$
is not k-choosable. Thus we have the following corollary.
Corollary 1.4 For the function
$\beta $
defined above,
Here is a brief outline of the proof of Theorem 1.2.
Assume G is a complete k-partite graph with
$2k+2$
vertices,
$G \ne K_{4, 2 \star (k-1)}, K_{3 \star (k+1)/2, 1 \star (k-1)/2}$
when k is even, and L is a k-list assignment of G. Let
$C_L= \bigcup _{v \in V}L(v)$
. The first step is to construct a family
$\mathcal {S}$
of independent sets that form a partition of
$V(G)$
. Let
$G/\mathcal {S}$
be the graph obtained from G by identifying each independent set
$S \in \mathcal {S}$
into a single vertex
$v_S$
. Let
$L_{\mathcal {S}}$
be the list assignment of
$G/\mathcal {S}$
defined as
$L_{\mathcal {S}}(v_S) = \bigcap _{ u \in S}L(u)$
. Build a bipartite graph
$B_{\mathcal {S}}$
with partite sets
$V(G/\mathcal {S})$
and
$C_L$
, with
$\{v_S, c\}$
be an edge if
$c \in L_{\mathcal {S}}(v_S)$
. If
$B_{\mathcal {S}}$
has a matching M that covers
$V(G/\mathcal {S})$
, then M defines an L-coloring of G, with each
$S \in \mathcal {S}$
be colored with the color matched to
$v_S$
in M.
Assume that there is no such a matching M, and hence by Hall’s theorem, there exists a subset
$X_{\mathcal {S}}$
of
$V(G/\mathcal {S})$
such that
$|Y_{\mathcal {S}}| < |X_{\mathcal {S}}|$
, where
$Y_{\mathcal {S}} = N_{B_{\mathcal {S}}}(X_{\mathcal {S}})$
. By analysing the lists
$L(v)$
and independent sets S in
$\mathcal {S}$
, the inequality
$|Y_{\mathcal {S}}| < |X_{\mathcal {S}}|$
may lead to a series of inequalities and eventually lead to a contradiction (which means that no such
$X_{\mathcal {S}}$
exists and hence the desired matching M exists).
Assume no contradiction is derived, and
$X_{\mathcal {S}}$
and
$Y_{\mathcal {S}}$
do exist. We choose
$X_{\mathcal {S}}$
so that
$|X_{\mathcal {S}}|-|Y_{\mathcal {S}}|$
is maximum. By Hall’s theorem, this implies that there is a matching
$M'$
in
$B_{\mathcal {S}}-(X_{\mathcal {S}} \cup Y_{\mathcal {S}})$
that covers
$V(G/\mathcal {S}) - X_{\mathcal {S}}$
.
Definition 1.1 A partial L-coloring of G is an L-coloring of an induced subgraph
$G[X]$
of G. Given an L-coloring
$\phi $
of
$G[X]$
,
$L^{\phi }$
is the list assignment of
$G-X$
defined as
$L^{\phi }(v) = L(v) - \phi (N_G(v) \cap X)$
for
$v \in V(G-X)$
. An L-coloring
$\phi $
of
$G[X]$
is a good partial L-coloring of G if the pair
$(G-X, L^{\phi })$
satisfies the condition of Theorem 1.2.
The matching
$M'$
constructed above defines a partial L-coloring
$\psi $
of G that colors vertices in
$\bigcup _{S \in V(G/\mathcal {S})-X_{\mathcal {S}}}S$
. One nice property of this partial coloring
$\psi $
is that if
$\{v\} \in X_{\mathcal {S}}$
is a singleton part of
$\mathcal {S}$
, then
$L^{\psi }(v) = L(v)$
(as
$L(v) \subseteq Y_{\mathcal {S}}$
). In other words some neighbours of v may have been colored, and yet v still has the same set of permissible colors.
By using this property, we want to extend
$\psi $
to a good partial L-coloring
$\phi $
of G, that colors a subset X of G. If this can be done, then
$G-X$
has an
$L^{\phi }$
-coloring
$\theta $
, and the union
$\phi \cup \theta $
would be an L-coloring of G.
For the plan above to work, the choice of the partition
$\mathcal {S}$
of
$V(G)$
in the first step is crucial. Indeed, Theorem 1.2 is equivalent to saying that there is a choice of
$\mathcal {S}$
such that
$B_{\mathcal {S}}$
has a matching M that covers
$V(G/\mathcal {S})$
. We usually start with a proper coloring f of G, which is not necessarily an L-coloring, but “close” to an L-coloring, and let
$\mathcal {S}$
be the color classes of f. In particular, the coloring f uses colors from
$C_L$
, and if
$f(v)=c \notin L(v)$
, then
$f^{-1}(c)=\{v\}$
and c is contained in many lists. The concept of “near acceptable” L-coloring is defined to capture the required properties needed for the plan above to work. Near acceptable L-coloring was first used in [Reference Noel, Reed and Wu17]. The definitions of near acceptable L-colorings for the proofs of Noel–Reed–Wu theorem and Theorem 1.2 are slightly different. The slight difference makes it more difficult to construct a near acceptable L-coloring of G for the proof of Theorem 1.2, while the proof of Noel–Reed–Wu theorem is already complicated. For the proof of Theorem 1.2, before constructing a near acceptable L-coloring of G, a pseudo-L-coloring of G is constructed as an intermediate step. In many cases, we need to repeatedly modify a pseudo L-coloring until we obtain a near acceptable L-coloring.
In Section 2, we prove a sufficient condition for a complete multipartite graph G with all parts of size at most 3 to be g-choosable for a given function
$g:V(G) \to \mathbb {N}$
. This will be used in later proofs. In Section 3, we fix some notation and present some basic properties of a minimum counterexample. In Section 4, we prove Theorem 1.2 for complete k-partite graphs with most parts of size at most 3. These graphs are special as there is little difference between these graphs and the critical graphs
$K_{4, 2 \star (k-1)}$
and
$K_{3 \star (k/2+1), 1 (k/2-1)}$
(for even k). In Section 5, we introduce the concept of pseudo-L-coloring of G and prove some properties of such colorings. In Section 6, we define the concept of near-acceptable L-coloring and show that the existence of a near-acceptable L-coloring of G implies the existence of a proper L-coloring of G. Some sufficient conditions for the existence of near-acceptable L-colorings of G are presented in Sections 7 and 8. A final contradiction is derived in Section 9.
2 Graphs with all parts of sizes at most 3
This section proves the following lemma, which gives a sufficient condition for
$g: V(G) \to \mathbb {N}$
, so that G is g-choosable when all parts of G have size at most 3. This lemma is analog to [Reference Kozik, Micek and Zhu14, Lemma 4], where a sufficient condition for G to be on-line g-choosable was given. The sufficient condition below is almost the same as that in [Reference Kozik, Micek and Zhu14, Lemma 5], except that for two vertices
$u,v$
in a 3-part of G, the upper bounds for the sum
$g(u)+g(v)$
in the two lemmas are different, and which is needed in later applications.
Lemma 2.1 Let G be a complete multipartite graph with parts of size at most
$3$
. Let
$\mathcal {A}, \mathcal {B}$
,
$\mathcal {C}$
,
$\mathcal {D}$
be a partition of the parts of G into classes such that
$\mathcal {A}$
and
$\mathcal {D}$
contain only parts of size
$1$
,
$\mathcal {B}$
contains all parts of size
$2$
and
$\mathcal {C}$
contains all parts of size
$3$
. Let
$k_1, k_2, k_3, d$
denote the cardinalities of classes
$\mathcal {A}$
,
$\mathcal {B}$
,
$\mathcal {C}$
,
$\mathcal {D}$
respectively. Suppose that classes
$\mathcal {A}$
and
$\mathcal {D}$
are ordered, i.e.,
$\mathcal {A}= (A_1, \ldots , A_{k_1})$
and
$\mathcal {D}=(D_1, \ldots , D_d)$
. If
$g:V(G)\to \mathbb {N}$
is a function for which the following hold:
then G is g-choosable.
Proof Assume the parts of G are partitioned into
$\mathcal {A}$
,
$\mathcal {B}$
,
$\mathcal {C}$
,
$\mathcal {D}$
and g is a function satisfying the inequalities (a-1)–(d-1), and L is a list assignment with
${|L(v)|}= g(v)$
. We shall color an independent set S of G with a color
$c \in \bigcap _{v \in S}L(v)$
. Let
$G'=G-S$
and
$L'$
be the list assignment of
$G'$
defined as
$L'(x) = L(x) -\{c\}$
for
$x \in V(G')$
and
$g'(v)=|L'(v)|$
. We shall verify that the pair
$(G', f')$
satisfies the condition of Lemma 2.1, and hence
$G'$
is
$L'$
-colorable by induction hypothesis (if
$|V(G)|=1$
, then the result is trivial). Together with the coloring of S with color c, we obtain an L-coloring of G.
In the following, we describe the choice of the independent set S. The color c is always an arbitrary color in
$\bigcap _{v\in S}L(v)$
. We describe briefly how to verify the fact that
$(G', g')$
satisfies the condition of Lemma 2.1 (the proof of Lemma 5 of [Reference Kozik, Micek and Zhu14] is similar, and contains more detailed explanations). The partition
$\mathcal {A}'$
,
$\mathcal {B}'$
,
$\mathcal {C}'$
,
$\mathcal {D}'$
of the parts of
$G'$
and the ordering of parts in
$\mathcal {A}'$
and
$\mathcal {D}'$
are inherited from the partition and the ordering of the parts of G, except that one part may have some vertices colored and remaining vertices form a part in another class. When a part from
$\mathcal {B}$
or
$\mathcal {C}$
has some vertices colored and the remaining vertex form a part in
$\mathcal {A}'$
or
$\mathcal {D}'$
, we also need to put it in a correct order. Denote by
$k^{\prime }_1,k^{\prime }_2,k^{\prime }_3, d'$
the cardinalities of
$\mathcal {A}'$
,
$\mathcal {B}'$
,
$\mathcal {C}'$
,
$\mathcal {D}'$
, respectively. To verify the inequalities, it suffices to show that with g replaced by
$g'$
,
$k_i$
replaced by
$k^{\prime }_i$
and d replaced by
$d'$
, the amount reduced on the left hand side is no more than the amount reduced on the right hand side.
The choice of S is determined in 8 cases. For
$ 2 \le i \le 8$
, Case i is considered only if all cases j with
$j \le i-1$
do not apply.
-
(1) If there exists $C \in \mathcal {B} \cup \mathcal {C}$
for which
$\bigcap _{v\in C}L(v) \ne \emptyset $
, then
$S=C$
. Verification: For (a-1),(b-1),(c-1), (d-1), the left hand side is reduced by at most 1 (i.e.,
$g'(v) \ge g(v)-1$
), and the right hand side is reduced by at least 1. (For example, consider (a-1):
$k^{\prime }_2+k^{\prime }_3+i = k_2+k_3+i - 1$
). For (b-2), (c-2), the left hand side is reduced by at most 2 (i.e.,
$g'(u)+g'(v) \ge g(u)+g(v)-2$
), and the right hand side is reduced by at least 2. For (c-3), the left hand side is reduced by at most 3 (i.e.,
$\sum _{v \in C}g'(v) \ge \sum _{v \in C}g(v)-3$
), and the right hand side is reduced by at least 3. -
(2) If there exist $ C=\{u,v, w\} \in \mathcal {C}$
with
$g(u)+g(v)= 2 k_3 +2k_2+ k_1$
, and
$L(u)\cap L(v) \ne \emptyset $
, then
$S=\{u,v\}$
. Verification: The part
$\{w\}$
of
$G'$
is the last member of
$\mathcal {D}'$
. Thus
$k^{\prime }_3=k_3-1$
and
$d'=d+1$
. Note that
$g'(w)=g(w) \ge 4k_3+3k_2+2k_1+d-1 - (2k_3+2k_2+k_1) = 2k_3+k_2+k_1+d-1 = 2k^{\prime }_3+k^{\prime }_2+k^{\prime }_1+d'$
. The other inequalities are verified as in Case 1. -
(3) If there exists $C=\{v,u,w\} \in \mathcal {C}$
,
$g(v)=k_2+k_3$
,
$L(v) \cap L(u) \neq \emptyset $
, then
$S=\{u, v\}$
. Verification: The part
$\{w\}$
of
$G'$
is the last member of
$\mathcal {A}'$
. Thus
$k^{\prime }_3=k_3-1$
and
$k^{\prime }_1=k_1+1$
. Note that
$g'(w)=g(w) \ge 2k_3+2k_2+k_1 - (k_3+k_2) = k_3+k_2+k_1 = k^{\prime }_3+k^{\prime }_2+k^{\prime }_1$
. For
$u,v \in C \in \mathcal {C}$
, either
$g(u)+g(v) \ge 2k_3+2k_2+k_1+1$
or
$g'(u)+g'(v) \ge g(u)+g(v)-1$
(as Case 2 does not apply). Hence (c-2) holds for
$(G',g')$
. As Case 1 does not apply, the left hand side of (c-3) reduces by at most 2, and the right hand side is reduced by 2. Hence (c-3) holds for
$(G',g')$
as Case 1 does not apply. The other inequalities are verified as in Case 1. -
(4) If there exists $C=\{v,u,w\} \in \mathcal {C}$
,
$g(v)=k_2+k_3$
,
$L(v) \cap (L(u) \cup L(w)) = \emptyset $
, then
$S=\{v\}$
. Verification: In the remaining graph
$G'=G-v$
, the two vertices
$u,w$
are identified into a single vertex
$u^*$
with
$L'(u^*) = L(u) \cap L(w)$
. The set
$\{u^*\}$
is the last member of
$\mathcal {A}'$
. So
$k^{\prime }_3=k_3-1, k^{\prime }_1=k_1+1$
. Note that $$\begin{align*}g(u)+g(w)\geq (4k_3+3k_2+2k_1+d-1)-(k_3+k_2)=3k_3+2k_2+2k_1+d-1. \end{align*}$$
On the other hand the total number of colors is at most $|V|-1 = 3 k_3 +2k_2+ k_1 +d-1$
. As
$L(v)$
is disjoint with
$L(u)\cup L(w)$
, we have
${|L(u ) \cup L( w)|} \leq 2 k_3 +k_2+k_1+d -1$
. Hence $$\begin{align*}|L'(u^*)| = {|L(u) \cap L(w)|} \geq k_3 + k_2+k_1 =k^{\prime}_3+k^{\prime}_2+k^{\prime}_1. \end{align*}$$
Note that for $C \in \mathcal {C}$
,
$\sum _{v \in C}g'(v) \ge \sum _{v \in C}g(v)-2$
, as Case 1 does not apply. Hence (c-3) holds for
$(G',g')$
. The other inequalities are verified as in Case 3. -
(5) If there exists $ B=\{u,v\} \in \mathcal {B}$
,
$g(v)=k_2+k_3$
, then
$S=\{v\}$
. Verification: The part
$\{u\}$
of
$G'$
is the last member of
$\mathcal {D}'$
. Thus
$k^{\prime }_2=k_2-1$
and
$d'=d+1$
. Note that
$g'(u)=g(u) \ge 3k_3+2k_2+k_1+d - (k_3+k_2) = 2k_3+k_2+k_1+d = 2k^{\prime }_3+k^{\prime }_2+k^{\prime }_1+d'$
. For
$B'=\{x,y\} \in \mathcal {B}$
, since Case 1 does not apply,
$g'(x)+g'(y) \ge g(x)+g(y)-1$
. So (b-2) holds for
$(G',g')$
. The other inequalities are verified as in Case 4. -
(6) If $k_1 \ne 0$
and
$A_1=\{v\}$
, then
$S=\{v\}$
. Verification: In this case,
$k^{\prime }_1=k_1-1$
. As Cases 2,3,4 do not apply, (b-1), (c-1), and (c-2) were not tight for g, and hence they hold for
$(G',g')$
. Also for (a-1), the index of each member reduces by 1, and hence the right hand side reduces by 1, so it holds for
$(G',g')$
. The other inequalities are verified as in Case 5. -
(7) Assume $k_3 \ne 0$
and
$C=\{u,v,w\} \in \mathcal {C}$
. As
$|C_L| \le |V|-1= 3k_3+2k_2+k_1+d-1$
, So
$g(u)+g(v)+g(w) \ge 4k_3+3k_2+2k_1+d-1>|C_L|$
and there is a color c which appears in two of the three color sets
$L(u)$
,
$L(v)$
,
$L(w)$
, say
$c\in L(u)\cap L(v)$
. Let
$S=\{u,v\}$
. Verification: Let
$\{w\}$
be the only member of
$\mathcal {A}'$
. Then
$k^{\prime }_3 = k_3-1$
and
$k^{\prime }_1=k_1+1$
,
$g'(w)=g(w) \ge k_2+k_3=k^{\prime }_2+k^{\prime }_3+1=k^{\prime }_2+k^{\prime }_3+k^{\prime }_1$
. The other inequalities are verified as in Case 6. -
(8) If $ d> 0$
and
$D_1=\{v\}$
, then
$S=\{v\}$
. Verification: In this case,
$k_3=k_1=0$
and
$d'=d-1$
. (b-1) is not tight for g (as Case 5 does not apply), and hence holds for
$(G',g')$
. (b-2) holds for
$(G',g')$
as the left-hand size reduces by at most 1, and the right hand side reduces by 1. For other member of
$\mathcal {D}'$
, its index is recued by 1, and hence (d-1) holds for
$(G',g')$
. Note that
$k_1,k_3=0$
, so the other inequalities are vacant.
Assume all the cases above do not apply. Then
$G=K_{2 \star k_2 }$
, i.e., G consists of
$k_2$
parts of size 2, and
$g(v) \ge k_2$
for each vertex v. It is well-known [Reference Erdős, Rubin and Taylor4] that in this case, G is g-choosable.
3 Some notation and basic properties for a minimum counterexample
By a counterexample of Theorem 1.2, we mean a pair
$(G,L)$
such that G is a complete multipartite graph and L is a list assignment of G that satisfy the condition of Theorem 1.2, and G is not L-colorable. We say
$(G,L)$
is a minimal counterexample to Theorem 1.2 if
$(G,L)$
is a counterexample to Theorem 1.2 with
-
(1) $|V(G)|$
minimum, -
(2) subject to (1), with $|C_L|$
minimum (recall that
$C_L=\bigcup _{v \in V}L(v)$
),
It is well-known [Reference Kierstead11] that
$|C_L| < |V(G)|$
. Let
In the remainder of this paper, we assume that
$(G,L)$
is a minimum counterexample to Theorem 1.2. Assume G is a complete k-partite graph. By Noel–Reed–Wu theorem, we know that k-chromatic graphs with at most
$2k+1$
vertices are k-choosable and hence G has exactly
$2k+2$
vertices, and
A part of G of size i (respectively, at least i or at most i) is called a i-part (respectively,
$i^+$
-part, or
$i^-$
-part). Let
Let
$p_i$
,
$p_i^+$
and
$p_i^-$
be the number of i-parts,
$i^+$
-parts and
$i^-$
-parts, respectively.
For a subset X of
$V(G)$
, let
For three vertices
$x,y,z$
of G, let
For
$c \in C_L$
and
$C' \subseteq C_L$
, let
For a part P of G and integer i, let
.
Assume
$\mathcal {S}$
is a partition of
$V(G)$
into a family of independent sets. Each
$S \in \mathcal {S}$
is called an
$\mathcal {S}$
part. Recall that
$G/\mathcal {S}$
is the graph obtained from G by identifying each part
$S \in \mathcal {S}$
into a single vertex
$v_S$
, and
$L_{\mathcal {S}}$
is the list assignment of
$G/\mathcal {S}$
defined as
$L_{\mathcal {S}}(v_S)=\bigcap _{v \in S}L(v)$
. If
$S=\{v\}\in \mathcal {S}$
consists of a single vertex of G, then we denote
$v_S$
by v. In this case,
$L_{\mathcal {S}}(v)=L(v)$
. For the partitions
$\mathcal {S}$
constructed in this paper, most parts of
$\mathcal {S}$
are singletons. To define
$\mathcal {S}$
, it suffices to list its non-singleton parts.
Recall that
$B_{\mathcal {S}}$
is the bipartite graph with partite sets
$V(G/\mathcal {S})$
and
$C_L$
, in which
$\{v_S,c\}$
is an edge if and only if
$c \in L_{\mathcal {S}}(v_S)$
. A matching M in
$B_{\mathcal {S}}$
covering
$V(G/\mathcal {S})$
induces an
$L_{\mathcal {S}}$
-coloring of
$G/\mathcal {S}$
, which in turn induces an L-coloring of G. Since G is not L-colorable, no such matching M exists. By Hall’s theorem, there is a subset
$X_{\mathcal {S}}$
of
$V(G/\mathcal {S})$
such that
$|X_{\mathcal {S}}|> |N_{B_{\mathcal {S}}}(X_{\mathcal {S}})|$
.
We denote by
$X_{\mathcal {S}}$
a subset of
$V(G/\mathcal {S})$
for which
$|X_{\mathcal {S}}| - |N_{B_{\mathcal {S}}}(X_{\mathcal {S}})|$
is maximum. Let
The choice of
$X_{\mathcal {S}}$
implies that there is a matching
$M_{\mathcal {S}}$
in
$B_{\mathcal {S}} - (X_{\mathcal {S}} \cup Y_{\mathcal {S}})$
that covers all vertices in
$V(G/\mathcal {S}) - X_{\mathcal {S}}$
. The matching
$M_{\mathcal {S}}$
defines a partial coloring
$\psi _{\mathcal {S}}$
of
$G[\bigcup _{S \in \mathcal {S}-X_{\mathcal {S}}}S]$
with colors from
$C_L-Y_{\mathcal {S}}$
.
These notation will be used throughout the whole paper.
Observation 3.1 The following easy facts will be used often in the argument.
-
(1) There is an injective mapping $\phi : C_L \to V$
such that
$c \in L(\phi (c))$
. -
(2) If f is a proper coloring of G, then there is a surjective proper coloring $g:V\to C_L$
such that for every vertex v,
$g(v)\in L(v)$
or
$g(v)=f(v)$
. -
(3) No two vertices in the same part of G have the same list, and no color is contained only in the lists of vertices in a same part.
-
(4) $G\neq K_{4,2\star (k-1)}$
for any k and
$|T|\ge 1$
.
Proof (1) is well-known ([Reference Noel, Reed and Wu17, Corollary 1.8]) and also easy to verify (use the minimality of
$|C_L|$
).
(2) was proved in [Reference Noel, Reed and Wu17, Proposition 1.13].
(3) If
$u,v$
are in the same part and
$L(u) = L(v)$
, then By Noel–Reed–Wu theorem, there is a proper L-coloring f of
$G-u$
, which extends to a proper L-coloring of G by letting
$f(u)=f(v)$
.
If there is a color c such that
$L^{-1}(c) \subseteq P_i$
for some part
$P_i$
of G, then by Noel–ReedWu theorem,
$G-L^{-1}(c)$
has an L-coloring f, which extends to an L-coloring of G by coloring vertices in
$L^{-1}(c)$
with color c.
(4) It was proved in [Reference Enomoto, Ohba, Ota and Sakamoto3] that
$K_{4,2\star (k-1)}$
is not k-choosable if and only if k is even. By our assumption,
$G\neq K_{4,2\star (k-1)}$
for even k. Thus
$G\neq K_{4,2\star (k-1)}$
for any k. It was proved in [Reference Gravier and Maffray6] that
$G=K_{3\star 2, 2 \star (k-2)}$
is k-choosable. Using the fact that
$|V(G)|=2k+2$
, it is easy to see that
$|T| \ge 1$
.
Lemma 3.2 If P is a
$2^+$
-part of G, then
$\bigcap _{v\in P}L(v)=\emptyset $
. Consequently for each color
$c \in C_L$
,
$|L^{-1}(c)| \le k+p_1+2$
.
Proof Assume the lemma is not true. We choose such a part P of maximum size, and color vertices in P by a common color c. Let
$L'(v) = L(v)-\{c\}$
for
$v \in V(G)-P$
. If
$|P| \ge 3$
, then
$L'$
and
$G-P$
satisfies the condition of Noel–Reed–Wu theorem and hence
$G-P$
has an
$L'$
-coloring.
Assume
$|P|=2$
. By (4) of Observation 3.1,
$G-P \ne K_{4, 2 \star (k-2)}$
. If
$G-P \ne K_{3 \star (q+1), 1 \star (q-1)}$
, then by the minimality of G,
$G-P$
has an
$L'$
-coloring. If
$G-P = K_{3 \star (q+1), 1 \star (q-1)}$
, then since each 3-part P has at most two vertices v for which
$c \in L(v)$
, it is straightforward to verify that
$G-P$
and
$L'$
satisfy the condition of Lemma 2.1. Hence
$G-P$
has an
$L'$
-coloring.
For any color
$c \in C$
, each
$2^+$
-part contains a vertex
$v \notin L^{-1}(c)$
. So
This completes the proof of Lemma 3.2.
4 Graphs with most parts of size at most 3
In this section, we consider complete k-partite graphs whose most parts are
$3^-$
-parts.
Let
Theorem 4.1
$G \notin \mathcal {G}_1 \cup \mathcal {G}_2$
.
We may assume that
$k \ge 8$
, as for
$k \le 7$
, we can check directly the graphs in
$\mathcal {G}_1, \mathcal {G}_2$
are k-choosable.
Assume
$G \in \mathcal {G}_1 \cup \mathcal {G}_2$
. We order the parts of G as
$ P_1,P_2, \ldots , P_k$
so that
-
• if $G \in \mathcal {G}_1$
, then
$P_1$
is the 5-part and
$P_2, P_3,\ldots , P_q$
are
$3$
-parts with
$\Lambda _{P_2,2}\ge \Lambda _{P_3,2}\ge \ldots \ge \Lambda _{P_q,2}$
; -
• if $G \in \mathcal {G}_2$
, then the first a parts are the 4-parts of G, and
$P_{a+1}, P_{a+2},\ldots , P_q$
are
$3$
-parts with
$\Lambda _{P_2,2}\ge \Lambda _{P_3,2}\ge \ldots \ge \Lambda _{P_q,2}$
. If
$a =2$
, then order
$P_1,P_2$
so that
$\Lambda _{P_1,3} \ge \Lambda _{P_2,3}$
.
Let
For a 3-part
$P $
of G, we have
$3k \le \sum _{v \in P}|L(v)| \le |C_L|+|C_{P,2}| \le 2k+1+|C_{P,2}|$
. So
$|C_{P,2}| \ge k-1$
. As P has three 2-subsets, we have
$\Lambda _{P, 2} \ge (k-1)/3 \ge 2$
.
Claim 4.2 If
$G\in \mathcal {G}_1$
, then
$C_{P_1,4} = \emptyset $
and
$C_{P_1,3} \ne \emptyset $
.
Proof If
$c \in C_{P_1,4}$
, then we color vertices in
$L^{-1}(c) \cap P_1$
with color c, and let
$L'(v)= L(v)-\{c\}$
for
$v \in G-(L^{-1}(c) \cap P_1)$
. It is easy to verify that
$G'=G-(L^{-1}(c) \cap P_1)$
and
$L'$
satisfy the condition of Lemma 2.1 (with
$P_1-L^{-1}(c)$
being the last part in
$\mathcal {A}$
, and with
$\mathcal {D} = \emptyset $
), and hence
$G'$
is
$L'$
-colorable, and G is L-colorable, a contradiction.
If
$C_{P_1,3} = \emptyset $
, then each color
$c \in C_L$
is contained in
$L(v)$
for at most two vertices
$v \in P_1$
. Hence
$2(2k+1) \ge 2|C_L| \ge \sum _{v \in P_1}|L(v)| = 5k$
, which implies that
$k \le 2$
, a contradiction.
Claim 4.3
$G \ne K_{5,2\star (k-2),1}$
.
Proof If
$G=K_{5,2\star (k-2),1}$
, then fix a 3-subset
$S_1$
of
$P_1$
with
$\bigcap _{v \in S_1}L(v) \ne \emptyset $
. Let
$\mathcal {S}$
be the partition of
$0V(G)$
with one non-singleton part
$S_1$
. Then
$|V(G/\mathcal {S})|=2k$
and hence
$|X_{\mathcal {S}}|\le 2k$
and
$|Y_{\mathcal {S}}| \le 2k-1$
. By Lemma 3.2,
$|X_{\mathcal {S}} \cap P|\le 1$
for any 2-part P. So
$|X_{\mathcal {S}}|\le k+2$
and
$|Y_{\mathcal {S}}| \le k+1$
. On the other hand,
$|X_{\mathcal {S}}|\ge 2$
and hence
$v\in X_{\mathcal {S}}$
for some vertex v with
$|L_{\mathcal {S}}(v)|\ge k$
and hence
$|Y_{\mathcal {S}}| \ge k$
and
$|X_{\mathcal {S}}|\ge k+1$
, and hence
$|X_{\mathcal {S}} \cap P^{\prime }_1 | \ge 2$
. This in turn implies that
$|Y_{\mathcal {S}}|=k+1$
and hence
$|X_{\mathcal {S}}|=k+2$
. Then
$P^{\prime }_1\subseteq X_{\mathcal {S}}$
and
$|Y_{\mathcal {S}}|\ge |L_{\mathcal {S}}(P^{\prime }_1)| \ge k+2=|X_{\mathcal {S}}|$
(by Claim 4.2), a contradiction.
It follows from Observation 3.1 that
$G\neq K_{4,2\star (k-1)}$
for any k. As
$G \ne K_{5,2\star (k-2),1}$
, G has at least two
$3^+$
-parts. Therefore
For
$i=1,2,\ldots , i_0$
, we shall choose a subset
$S_i$
of
$P_i$
of size
$2$
or
$3$
, and let
$\mathcal {S}$
be the partition of
$V(G)$
with non-singleton parts
$\{S_1,S_2, \ldots , S_{i_0}\}$
. The rules for choosing the sets
$S_i$
will be given later.
For simplicity, in the graph
$G/\mathcal {S}$
, for
$i=1,2,\ldots , i_0$
, we denote
$v_{S_i}$
by
$z_i$
, and let
We denote by
$P^{\prime }_i$
the part of
$G/\mathcal {S}$
, where for
$1 \le i \le i_0$
,
$P^{\prime }_i$
is obtained from the part
$P_i$
by identifying
$S_i$
into a new vertex
$z_i$
, and for
$i_0+1 \le i \le k$
,
$P^{\prime }_i=P_i$
.
As
$i_0 \ge 2$
, we have
$|V(G/\mathcal {S})| \le 2k$
, and hence
We shall prove further upper and lower bounds for
$|X_{\mathcal {S}}|$
and
$|Y_{\mathcal {S}}|$
that eventually lead to a contradiction.
The details are delicate and a little complicated, which is perhaps unavoidable, as
$K_{4, 2 \star (k-1)}$
and
$K_{3 \star (k/2+1), 1 \star (k/2-1)}$
(for even integer k) are very close to graphs in
$\mathcal {G}_1 \cup \mathcal {G}_2$
, and they are not k-choosable. We divide the proofs for
$G \notin \mathcal {G}_1$
and
$G \notin \mathcal {G}_2$
into two subsections.
4.1
$G \notin \mathcal {G}_1$
Assume to the contrary that
$G \in \mathcal {G}_1$
.
The subsets
$S_i$
for
$i=1,2,\ldots , i_0$
are chosen as follows:
-
(1) $S_1$
is a 3-subset of
$P_1$
with
$|\bigcap _{v \in S_1}L(v)| =\Lambda _{P_1,3}$
. -
(2) For $2 \le i \le i_0$
,
$S_i$
is a 2-subset of
$P_i$
with
$|\bigcap _{v \in S_i}L(v)|=\Lambda _{P_i,2}$
.
Assume for
$i=2,3,\ldots , i_0$
,
$P_i=\{u_i,v_i,w_i\}$
and
$S_i=\{u_i, v_i\}$
.
Since
$|P_1-S_1|=2 $
, by (3) of Observation 3.1,
$|L(P_1-S_1)| \ge k+1$
. As
$(\bigcap _{v \in S_1} L(v)) \cap L(P_1-S_1) = \emptyset $
, we know that
It follows from the definition of
$\mathcal {S}$
that for
$i=1,2,\ldots , i_0$
,
$|L_{\mathcal {S}}(z_i)| \ge i_0$
.
If
$X_{\mathcal {S}} \subseteq Z$
and
$z_i \in X_{\mathcal {S}}$
for some
$i \le i_0$
, then we have
$|Y_{\mathcal {S}}| \ge |L_{\mathcal {S}}(z_i)| \ge i_0 \ge |X_{\mathcal {S}}|$
, a contradiction. Thus
$X_{\mathcal {S}} -Z \ne \emptyset $
. Let
$v \in X_{\mathcal {S}}-Z$
. Then
This implies that
$|X_{\mathcal {S}} \cap P^{\prime }_i| \ge 2$
for some i. As
$|L_{\mathcal {S}}(A)| \ge k+1$
for any 2-subset A of
$P^{\prime }_i$
(for any i), we have
Claim 4.4
$ |Y_{\mathcal {S}}| \ge k+i_0$
and hence
$|X_{\mathcal {S}}| \ge k+i_0+1$
.
Proof If there is an index
$ i_0+1 \le i \le q$
such that
$u,v \in X_{\mathcal {S}} \cap P^{\prime }_i$
, then
$ |Y_{\mathcal {S}}| \ge |L(u \vee v)| \ge 2k-|L(u \wedge v)| \ge 2k-i_0> k+i_0$
(as
$i_0 \le q-1 < k/2$
) and we are done.
Assume
$ |X_{\mathcal {S}} \cap P^{\prime }_i|\le 1$
for any
$ i_0+1 \le i \le q$
. If
$\{z_i, w_i\} \subseteq X_{\mathcal {S}}$
for some
$i \ge 2$
, then
$|Y_{\mathcal {S}}| \ge |L(w_i)|+|L_S(z_i)| +\ge k+i_0$
, and we are done. Otherwise,
$|X_{\mathcal {S}}| \ge k+2$
(by (4.3)) implies that
$P^{\prime }_1 \subseteq X_{\mathcal {S}}$
and
$|X_{\mathcal {S}}| = k+2$
. By (4.2),
$|Y_{\mathcal {S}}| \ge |L_{\mathcal {S}}(P^{\prime }_1)| \ge k+2$
, a contradiction.
Claim 4.5 If
$ |Y_{\mathcal {S}}| = k+i_0$
, then
$\Lambda _{P_i,2} = i_0$
for
$i=2,3,\ldots , i_0$
and there is an index
$2 \le i \le i_0$
such that
$P_i$
has a
$2$
-subset S with
$| \bigcap _{v \in S}L(v)| \ge 2$
and
$\bigcap _{v \in S}L(v) \cup L(P_i-S) \not \subseteq Y_{\mathcal {S}}$
.
Proof Assume
$|Y_{\mathcal {S}}|=k+i_0$
. Then
$|X_{\mathcal {S}}| \ge k+i_0+1$
.
By the argument in the proof of Claim 4.4, for any index
$i> i_0$
,
$|X_{\mathcal {S}} \cap P_i| \le 1$
. This implies that
$|X_{\mathcal {S}}| \le k+i_0+1$
, and hence
$|X_{\mathcal {S}}| = k+i_0+1$
and
$P^{\prime }_i \subseteq X_{\mathcal {S}}$
for
$i=1,2,\ldots , i_0$
. As
$|L_{\mathcal {S}}(P^{\prime }_i)| \ge k+i_0$
for
$2 \le i \le i_0$
, we conclude that for
$2 \le i \le i_0$
,
$Y_{\mathcal {S}} = L_{\mathcal {S}}(P^{\prime }_i)$
and
$\Lambda _{P_i,2}=i_0$
.
We shall find an index
$2 \le i \le i_0$
, a
$2$
-subset S of
$P_i$
with
$| \bigcap _{v \in S}L(v)| \ge 2$
and
$\bigcap _{v \in S}L(v) \cup L(P_i-S) \not \subseteq Y_{\mathcal {S}}$
.
Assume first that there is an index
$2 \le i \le i_0$
such that
$L(P_i) \not \subseteq Y_{\mathcal {S}}$
.
As
$L(w_i)\subseteq Y_{\mathcal {S}}$
, we may assume that there is a color
$c\in L(u_i)-Y_{\mathcal {S}}$
. If
$|L(v_i \wedge w_i)|\ge 2$
, then let
$S=\{v_i,w_i\}$
, we are done.
Assume
$|L(v_i \wedge w_i)|\le 1$
. This implies that
$ |L(v_i \vee w_i)|\ge 2k-1>k+i_0$
. So there is a color
$c'\in L(v_i) -Y_{\mathcal {S}}$
. If
$ |L(u_i \wedge w_i)|\ge 2$
, then let
$S=\{u_i,w_i\}$
, we are done. Assume
$|L(u_i \wedge w_i)|\le 1$
. Hence
This implies that
$k-3 \le i_0 \le q \le k/2$
, contrary to our assumption that
$k \ge 8$
.
Assume next that
$L(P_i)=Y_{\mathcal {S}}$
for
$2\le i\le i_0$
. As each color in
$L(P_i)$
is contained in at most two lists of vertices of
$P_i$
, we have
$2(k+i_0) \ge 3k$
, i.e.,
$i_0 \ge k/2$
. Hence
$i_0=k/2=q$
and
$G=K_{5,3\star (q-1), 1\star q}$
.
For each singleton part
$\{v\}$
of G, we have
$v \in X_{\mathcal {S}}$
and hence
$L(v) \subseteq Y_{\mathcal {S}}$
for each singleton part
$\{v\}$
. Thus
$L(\bigcup _{i=2}^kP_i) = Y_{\mathcal {S}}$
.
Since
$C_{P_1,4}= \emptyset $
, we have
$|L(P_1)|\ge 5k/3> k+i_0 = |Y_{\mathcal {S}}|$
. Let
$c\in L(P_1)-Y_{\mathcal {S}}$
. Then
$c $
is contained in the lists of vertices in
$P_1$
only, in contradiction to Observation 3.1.
If
$|Y_{\mathcal {S}}| = k+i_0$
, then as
$\Lambda _{P_i, 2}=i_0$
for
$2\le i \le i_0$
, we may assume that
$S^{\prime }_2=\{u_2, w_2\}$
is a 2-subset of
$P_2$
for which
$| \bigcap _{v \in S^{\prime }_2}L(v)| \ge 2$
and
$\bigcap _{v \in S^{\prime }_2}L(v) \cup L(P_2-S^{\prime }_2) \not \subseteq Y_{\mathcal {S}}$
.
We let
$\mathcal {S}'$
be the partition of
$V(G)$
whose non-singleton parts are obtained from that of
$\mathcal {S}$
by replacing
$S_2$
with
$S^{\prime }_2$
, i.e.,
$\mathcal {S}' = \{S_1, S^{\prime }_2,S_3, \ldots , S_{i_0}\}$
.
Instead of
$G/\mathcal {S}$
, we consider the graph
$G/\mathcal {S}'$
. We still have (4.3), i.e.,
Then analog to the proof of Claim 4.4, we can show that
Let
$\mathcal {S}" = \mathcal {S}$
if
$|Y_{\mathcal {S}}| \ge k+i_0+1$
, and
$\mathcal {S}" = \mathcal {S}'$
if
$|Y_{\mathcal {S}}| =k+i_0$
. Then
For simplicity, we assume that
$\mathcal {S}"=\mathcal {S}$
. Then
$|X_{\mathcal {S}}| \ge k+i_0+2$
implies that
$|X_{\mathcal {S}} \cap P_i| \ge 2$
for some
$i \ge i_0+1$
. Assume
$\{u,v\} \subseteq X \cap P_i$
for some
$i \ge i_0+1$
. Then
Since
$X_{\mathcal {S}}$
contains at most one vertex of any 2-part, we have
If for some
$i \ge i_0+1$
,
$ P_i=\{u_i,v_i, w_i\} \subseteq X_{\mathcal {S}}$
, then
Hence
$k+2q+1-i_0 \ge |X_{\mathcal {S}}| \ge 3k-3i_0+1$
, which implies that
$k \le q+i_0\le 2q-1$
, in contrary to
$k\ge 2q$
.
Thus
$|X_{\mathcal {S}} \cap P^{\prime }_i| \le 2$
for
$i \ge i_0+1$
. This implies that
$|X_{\mathcal {S}}| \le k+q+1$
.
On the other hand,
$|Y_{\mathcal {S}}| \ge 2k-i_0$
(by (4.4)) implies that
$|X_{\mathcal {S}}| \ge 2k-i_0+1$
. Hence
$ k{\kern-1pt}+{\kern-1pt}q{\kern-1pt}+{\kern-1pt}1 {\kern-1pt}\ge{\kern-1pt} |X_{\mathcal {S}}| \ge 2k{\kern-1pt}-{\kern-1pt}i_0+1$
, which implies that
$k {\kern-1pt}\le{\kern-1pt} i_0{\kern-1pt}+{\kern-1pt}q {\kern-1pt}\le{\kern-1pt} 2q{\kern-1pt}-{\kern-1pt}1$
, in contrary to
$k\ge 2q$
.
This completes the proof that
$G \notin \mathcal {G}_1$
.
4.2
$G \notin \mathcal {G}_2$
Assume to the contrary that
$G \in \mathcal {G}_2$
.
Claim 4.6 Assume P is a 4-part of G and
$\Lambda _{P,3} \le 1$
. Then
$\Lambda _{P, 2} \ge 2$
. If
$|\Lambda _{P,2}|\ge 3$
, then for any 2-subset S of P with
$| \bigcap _{v \in S}L(v)| = \Lambda _{P, 2}$
, for any
$x\in P-S$
,
If
$\Lambda _{P, 2} = 2$
, then there exists a 2-subset S of P such that
$| \bigcap _{v \in S}L(v) \cap C_{P,2}| = 2$
, and hence for any
$x\in P-S$
,
$|\bigcap _{v\in S}L(v) \cup L(x)|\ge k+2$
.
Proof Assume P is a 4-part of G and
$\Lambda _{P,3} \le 1$
. Assume
$\Lambda _{P,2}\ge 3$
and S is a 2-subset of P with
$| \bigcap _{v \in S}L(v)| = \Lambda _{P, 2}$
. Then for any
$x\in P-S$
, since
$|\bigcap _{v \in S}L(v) \cap L(x)| \le \Lambda _{P,3} \le 1$
, we have
Assume
$\Lambda _{P,2} \le 2$
. As P has four 3-subsets, we have
$|C_{P,3}| \le 4$
. As
$\sum _{i=1}^3 i |C_{P,i}| = \sum _{v \in P}|L(v)| \ge 4k$
and
$\sum _{i=1}^3|C_{P,i}| \le |C_L| \le 2k+1$
, it follows that
$|C_{P,2}| \ge 2k-9 \ge 7$
(as
$k \ge 8$
). Since P has six 2-subsets, there exists a 2-subset S of P such that
$|\bigcap _{v \in S}L(v) \cap C_{P,2}| \ge 2$
. Hence
$\Lambda _{P,2} \ge 2$
and therefore
$\Lambda _{P,2} = 2$
. Moreover, there exists a 2-subset S of P such that
$| \bigcap _{v \in S}L(v) \cap C_{P,2}| = 2$
. For any
$x\in P-S$
,
Definition 4.1 For
$i=1,2,\ldots , i_0$
, we choose a subset
$S_i$
of
$P_i$
of size
$2$
or
$3$
as follows:
-
(1) For $a+1 \le i \le i_0$
,
$S_i$
is a 2-subset of
$P_i$
with
$|\bigcap _{v \in S_i}L(v)| = \Lambda _{P_i,2}$
. -
(2) If $a=1$
and
$\Lambda _{P_1,3}>0$
, then let
$S_1$
be a 3-subset of
$P_1$
with
$|\bigcap _{v \in S_1}L(v)| = \Lambda _{P_1,3}$
. Otherwise, let
$S_1$
be a 2-subset of
$P_1$
with
$|\bigcap _{v \in S_1}L(v)| =\Lambda _{P_1,2}$
. -
(3) Assume $a=2$
.-
(i) If $\Lambda _{P_2,3} \ge 2$
, then for
$i=1,2$
, let
$S_i$
be a 3-subset of
$P_i$
with
$|\bigcap _{v \in S_i}L(v)| = \Lambda _{P_i,3}$
. -
(ii) If $\Lambda _{P_1,3}> 0$
and
$\Lambda _{P_2,3} \le 1$
, then let
$S_1$
be a 3-subset of
$P_1$
with
$|\bigcap _{v \in S_1}L(v)|= \Lambda _{P_1,3}$
, and let
$S_2$
be a 2-subset of
$P_2$
such that-
(A) $| \bigcap _{v \in S_2}L(v)| = \Lambda _{P, 2}$
, -
(B) $|\bigcap _{v\in S_2}L(v) \cup L(x)|\ge k+2$
for any
$x\in P_2-S_2$
, -
(C) Subject to (A) and (B), $|L_{\mathcal {S}}(P^{\prime }_1) \bigcup L(P_2-S_2)|$
is maximum.
-
-
(iii) If $\Lambda _{P_1,3}=0$
, then for
$i=1,2$
, let
$S_i$
be a 2-subset of
$P_i$
with
$|\bigcap _{v \in S_i}L(v)| = \Lambda _{P_i,2}$
, such that
$|\bigcap _{v\in S_i}L(v) \cup L(x)|\ge k+2$
for any
$x\in P_i-S_i$
and subject to this condition,
$|L_{\mathcal {S}}(P^{\prime }_1)\bigcup L_{\mathcal {S}}(P^{\prime }_2)|$
is maximum.
-
The existence of the 2-subset S in (ii) and (iii) has been proved in Claim 4.6.
It follows from the definition of
$\mathcal {S}$
that for
$i=1,2,\ldots , i_0$
,
$|L_{\mathcal {S}}(z_i)| \ge i$
.
The same argument as in the previous subsection shows that
Claim 4.7 If
$|P_i|=4$
, then
$|X_{\mathcal {S}} \cap P^{\prime }_i| \le 2$
.
Proof Assume
$P_i=\{u_i,v_i,x_i,y_i\}$
. Then
$2 \le |P^{\prime }_i| \le 3$
. If
$|P^{\prime }_i| =2$
, then the conclusion is trivial.
Assume
$|P^{\prime }_i| =3$
and assume to the contrary of the claim that
$P^{\prime }_i = \{z_i, x_i, y_i\} \subseteq X_{\mathcal {S}}$
, where
$z_i$
is the identification of
$u_i$
and
$v_i$
. In this case,
$L_{\mathcal {S}}(z_i) = L(u_i \wedge v_i)$
and
$L_{\mathcal {S}}(x_i)=L(x_i)$
,
$L_{\mathcal {S}}(y_i) = L(y_i)$
.
If
$\Lambda _{P_i,3}=0$
, then
$L_{\mathcal {S}}(z_i)\cap L(x_i \vee y_i)=\emptyset $
. By the choice of
$S_i$
,
$|L(x_i \wedge y_i)| \le |L_{\mathcal {S}}(z_i)|$
and hence
$|L(x_i \vee y_i)| \ge 2k - |L_{\mathcal {S}}(z_i)|$
. Therefore
$|Y_{\mathcal {S}}| \ge |L_{\mathcal {S}}(z_i)| + |L(x_i \vee y_i)| \ge 2k$
, in contrary to (4.1).
If
$\Lambda _{P_i,3}>0$
, then by the choice of
$S_i$
, we know that
$i=a=2$
,
$\Lambda _{P_2,3}=1$
and
$|S_1|=3$
,
$|P^{\prime }_1|=2$
. Therefore
$|X_{\mathcal {S}}| \le |V(G/\mathcal {S})| \le 2k-1$
, and
$|Y_{\mathcal {S}}| \le 2k-2$
.
Assume
$S_2=\{u_2,v_2\}$
. By the choice of
$S_2$
(see Claim 4.6),
$|L_{\mathcal {S}}(z_2)| \ge |L(x_i \wedge y_i)|$
and
$|L_{\mathcal {S}}(z_i) \cap L(x_i \vee y_i)| \le |L_{\mathcal {S}}(z_i) \cap L(x_i)| + |L_{\mathcal {S}}(z_i) \cap L(y_i)| \le 2 \Lambda _{P_i,3} =2$
. Hence
$|Y_{\mathcal {S}}| \ge |L_{\mathcal {S}}(z_i)| + |L(x_i \vee y_i)|-2 \ge 2k-2$
. So
$|X_{\mathcal {S}}| = 2k-1$
and
$|Y_{\mathcal {S}}|=2k-2$
, and hence
$ X_{\mathcal {S}}= V(G/\mathcal {S})$
. This implies that
$i_0=2$
.
By Lemma 3.2, G has no
$2$
-part. Assume
$P_3=\{u_3,v_3,w_3\}$
. Then since
$\Lambda _{P_3,2} \le 2$
, and
$P_3$
has three 2-subsets, we know that
$|C_{P_3,2}| \le 6$
. Therefore
a contradiction (as
$k\ge 8$
).
Since
$3p_3^++2p_2+p_1 \le 2k+2= 2(p_1+p_2+p_3^+)+2$
and
$G\neq K_{3\star (k/2+1), 1\star (k/2-1)}$
(i.e.,
$k\neq 2q-2$
), we have
Note that
$X_{\mathcal {S}}$
contains at most one vertex of any 2-part. Combining with Claim 4.7, we have
Claim 4.8 For any
$i \ge i_0+1$
,
$|X_{\mathcal {S}} \cap P_i| \le 1$
.
Proof If
$i\ge q+1$
, then
$P_i$
is
$2^-$
-part and hence
$|P_i\cap X_{\mathcal {S}}|\le 1$
(by Lemma 3.2 and (4.1).
Assume
$i_0+1\le i\le q$
.
First we prove that
$|X_{\mathcal {S}} \cap P_i| \le 2$
. Assume to the contrary that
$|X_{\mathcal {S}} \cap P_i| = 3$
for some
$i \ge i_0+1$
. Assume
$ P_i=\{u_i,v_i, w_i\}$
. Then
Hence
$k+2q-i_0 \ge |X_{\mathcal {S}}| \ge 3k-3i_0+1$
, which implies that
$2k+1 \le 2q+2i_0\le 4q$
. As
$k\ge 2q-1$
, we have
$k=2q-1$
. Hence
$q=i_0$
, in contrary to
$i_0+1\le i\le q$
.
Since
$|X_{\mathcal {S}} \cap P_i| \le 2$
for all
$i \ge i_0+1$
, we know that
$|X_{\mathcal {S}}| \le k+q$
(by Claim 4.7).
If
$|X_{\mathcal {S}} \cap P_i| = 2$
for some
$q \ge i \ge i_0+1$
, then
$|Y_{\mathcal {S}}| \ge 2k-i_0$
. Hence
$ k+q \ge |X_{\mathcal {S}}| \ge 2k-i_0+1$
, which implies that
$k = 2q-1$
and
$i_0=q$
, again in contrary to
$i_0+1\le i\le q$
.
It follows from Claims 4.7 and 4.8 that
$|X_{\mathcal {S}}| \le k+i_0$
and hence
$|Y_{\mathcal {S}}| \le k+ i_0-1$
.
Thus
$|X_{\mathcal {S}} \cap P^{\prime }_i| \le 1$
for any
$ a+1 \le i\le i_0$
. Combining with Claim 4.8, we know that
$|X_{\mathcal {S}} \cap P^{\prime }_i| \le 1$
for any
$i \ge a+1$
. Since
$|X_{\mathcal {S}}| \ge k+2$
(by (4.5)), it follows from Claim 4.7 that
$a=2$
and
$|X_{\mathcal {S}} \cap P^{\prime }_{i}| =2$
for
$i=1,2$
, and
For
$i=1,2$
, assume
$P_i=\{u_i,v_i,x_i,y_i\}$
.
If
$\Lambda _{P_2,3} \ge 2$
, then
$|S_2|=3$
, say
$S_2=\{u_2,v_2,x_2\}$
. Then
$|Y_{\mathcal {S}}|\ge |L_{\mathcal {S}}(z_2)|+|L(P_2-S_2)|\ge k+2$
, a contradiction.
Assume
$\Lambda _{P_2,3} \le 1$
. Then (ii) or (iii) holds, and
$|S_2|=2$
, say
$S_2=\{u_2,v_2\}$
. If
$z_2 \in X_{\mathcal {S}}$
, say
$P^{\prime }_2\cap X_{\mathcal {S}}=\{z_2,x_2\}$
, then
$|Y_{\mathcal {S}}|\ge |L_{\mathcal {S}}(z_2)\cup L(x_2)|\ge k+2$
(by Claim 4.6), contrary to (4.6).
Assume
$z_2 \notin X_{\mathcal {S}}$
. Then
$x_2,y_2 \in X_{\mathcal {S}}$
. Now
$|L(x_2 \vee y_2)| \le |Y_{\mathcal {S}}| = k+1$
implies that
$|L(x_2 \vee y_2)|=k+1$
and
$|L(x_2 \wedge y_2)|=k-1$
. This implies that
$\Lambda _{P_2,2}=k-1$
and hence
$|L(u_2 \wedge v_2)|=k-1$
. As
$k\ge 8$
, i.e.,
$\Lambda _{P_2,2}=k-1\ge 7$
, it follows from Claim 4.6 that
$| L(x_2\wedge y_2)| = \Lambda _{P, 2}\ge 2$
and
$|L(x_2\wedge y_2) \cup L(v)|\ge k+2$
for any
$v\in P_2-\{x_2,y_2\}$
.
If (ii) holds, say
$S_1=\{u_1,v_1,x_1\}$
, then
$L(u_2\vee v_2)=L_{\mathcal {S}}(z_1)\cup L(y_1)$
. This implies that
$L(x_2\vee y_2)=L_{\mathcal {S}}(z_1)\cup L(y_1)$
, for otherwise, by see (ii), we should have chosen
$S_2=\{x_2,y_2\}$
. So
$|L(P_2)|=k+1$
. Hence
This implies that
$L(x_2\wedge y_2) \cap L(u_2 \wedge v_2) \ne \emptyset $
, in contrary to Lemma 3.2.
Assume (iii) holds, and for
$i=1,2$
,
$P_i=\{u_i,v_i, x_i,y_i\}$
and
$S_i=\{u_i,v_i\}$
. If
$z_i\in X_{\mathcal {S}}$
for some
$i=1,2$
, then by Claim 4.6,
$|L_{\mathcal {S}}(z_i)| \ge 2$
and hence
$|Y_{\mathcal {S}}| \ge |L_{\mathcal {S}}(P^{\prime }_i)| \ge k+2$
, contrary to (4.6).
Assume
$z_1, z_2 \notin X_{\mathcal {S}}$
. Then again by the choice of
$S_2$
, we have
$L(u_2 \vee v_2) = L(x_1 \vee y_1) = L(x_2 \vee y_2)$
,
$|L(x_2 \wedge y_2)| =|L(u_2 \wedge v_2)| = k-1$
, and
$|L(P_2) | =k+1$
. This leads to the same contradiction. This completes the proof of Theorem 4.1.
It was proved in [Reference Shen, He, Zheng, Wang and Zhang23] that
$K_{6, 2 \star (k-3), 1 \star 2}$
is k-choosable. Combining with Theorem 4.1, we conclude that
5 Pseudo-L-coloring
As described in Section 1, our strategy for proving Theorem 1.2 is to partition
$V(G)$
into a family
$\mathcal {S}$
of independent sets, so that either there is a matching
$M_{\mathcal {S}}$
in the bipartite graph
$B_{\mathcal {S}}$
that covers
$V(G/\mathcal {S})$
and hence produce an L-coloring of G, or using Hall’s theorem to produce a good partial L-coloring of G that leads to an L-coloring of G by using induction. The partition
$\mathcal {S}$
is obtained by constructing a proper coloring f of G, and the parts in
$\mathcal {S}$
are the color classes of f. For this strategy to succeed, the coloring f needs to have some nice property. In this section, we define the concept of pseudo-L-coloring of G, and study properties of the partition
$\mathcal {S}$
of
$V(G)$
induced by such colorings.
Definition 5.1 A pseudo L-coloring of G is a proper coloring f of G such that
$f(v) \in C_L$
for every vertex v, and if
$f(v)=c \notin L(v)$
, then
$f^{-1}(c)=\{v\}$
is a singleton f-class.
In a pseudo L-coloring f of G, if
$f(v) \not \in L(v)$
, then we say v is badly f-colored (or badly colored if f is clear from the context).
By Observation 3.1, if f is a pseudo-L-coloring of G, then there is a pseudo-L-coloring g of G such that
$g(G)=C_L$
and for every badly g-colored vertex v of G,
$g(v)=f(v)$
. In the following, we may assume that all the pseudo-L-colorings f satisfy
$f(G)=C_L$
. However, when we construct a pseudo-L-coloring f of G, we do not need to verify that
$f(G)=C_L$
(because if
$f(G) \ne C_L$
, then we change it to the pseudo-L-coloring g described above).
Definition 5.2 Assume f is a pseudo L-coloring of G. Let
${\mathcal {S}}_f$
be the family of f-classes, which is a partition of
$V(G)$
, i.e.,
${\mathcal {S}}_f=\{f^{-1}(c):c\in C_L\}$
where
$f^{-1}(c)$
is the set of all vertices colored by c under f. We denote
$G/\mathcal {S}_f$
,
$L_{\mathcal {S}_f}$
,
$B_{\mathcal {S}_f}$
,
$X_{\mathcal {S}_f}$
and
$Y_{\mathcal {S}_f}$
by
$G_f$
,
$L_f$
,
$B_f$
,
$X_f$
, and by
$Y_f$
, respectively.
The bipartite graph
$B_f$
with partite sets
$G_f$
and
$C_L$
. Vertices in
$G_f$
are f-classes, some of them are singleton classes represented by solid circles, and other are
$2^+$
-classes, represented by solid squares. The broken arrowed line indicate the coloring f. The edges of
$B_f$
are not drawn, and
$Y_{\mathcal {S}} = N_{B_{\mathcal {S}}}(X_{\mathcal {S}})$
. Vertex
$v^*$
is contained in
$X_{\mathcal {S}}$
but
$f(v^*)=c^* \notin Y_{\mathcal {S}}$
. So
$v^{\star }$
is a badly f-coloured vertex.
Figure 1: Long description
The diagram consists of two horizontal ovals representing partite sets.
Upper Set G sub f:
Contains seven vertices. Three are solid blue squares representing f-classes of size at least 2, and four are solid blue circles representing f-classes of size 1. A green dashed rectangle labeled X sub S encloses the first four vertices from the left (two squares and two circles). The fourth vertex in this set is a blue circle labeled v super star in red.
Lower Set C sub L:
Contains seven solid blue circles. A green dashed rectangle encloses the first three circles from the left. The fifth circle from the left is labeled c super star in red.
Mapping and Relationships:
Seven dashed arrows point from vertices in G sub f to vertices in C sub L.
- The first square in G sub f points to the first circle in C sub L.
- The second square in G sub f points to the third circle in C sub L.
- The first circle in G sub f points to the second circle in C sub L.
- The red-labeled v super star in G sub f points to the fifth circle in C sub L, which is labeled c super star.
- The third square in G sub f points to the sixth circle in C sub L.
- The third circle in G sub f points to the fourth circle in C sub L.
- The final circle in G sub f points to the final circle in C sub L.
Text at the bottom left states Y sub S = N sub B sub f (X sub S) in green. Centered at the bottom is the equation B sub f = (G sub f, C sub L).
In the remainder of this section, assume f is a pseudo L-coloring of G. In the graph
$G_f$
,
$f^{-1}(c)$
is identified into a single vertex. For simplicity, we denote this vertex by
$f^{-1}(c)$
. So
$f^{-1}(c)$
is both a subset of
$V(G)$
and a vertex of
$G_f$
. It will be clear from the context which one it is.
Since
$|X_f|> |Y_f|$
, there is a color class
$f^{-1}(c) \in X_f$
such that
$c \notin Y_f$
. Hence
$f^{-1}(c)$
is a singleton f-class
$\{v\}$
and v is badly colored by f.
For a subset Q of
$V(G_f)$
, let
$V(Q)$
be the subset of
$V(G)$
defined as
Let
$\ell $
be the number of f-classes
$f^{-1}(c)$
of size
$|f^{-1}(c)| \ge 2$
. As
$|V|> |C_L|$
,
$\ell \ge 1$
. On the other hand,
$\lambda = |V|-|C_L| \ge \ell $
and equality holds if and only if
$f(G)=C_L$
and each f-class has size at most 2.
Recall that there is a matching
$M_{\mathcal {S}_f}$
in
$B_f - (X_f \cup Y_f)$
that covers all vertices in
$V(G_f) - X_f$
. The matching
$M_{\mathcal {S}_f}$
defines a partial L-coloring of
$G[ \bigcup _{f^{-1}(c)\notin X_f}f^{-1}(c)]$
that colors vertices in
$f^{-1}(c)$
with
$c'$
, where
$\{c', f^{-1}(c)\} $
is an edge in
$M_{\mathcal {S}_f}$
. We denote this partial L-coloring of G by
$\psi _f$
. The matching
$M_{\mathcal {S}_f}$
maybe not unique. In this case, we let
$M_{\mathcal {S}_f}$
be an arbitrary matching that covers
$V(G_f) - X_f$
.
We extend
$\psi _f$
to a partial L-coloring
$\phi _f$
of G by coloring each f-classes
$f^{-1}(c) \in X_f$
of size at least 2 by color c. By definition of pseudo-L-coloring, for such an f-class
$f^{-1}(c)$
,
$c \in L_{\mathcal {S}}(f^{-1}(c))$
. So
$\phi _f$
is a proper L-coloring of G. Denote by X the set of vertices of G colored by
$\phi _f$
. Note that only those f-classes
$f^{-1}(c)$
of size at least 2 contained in
$X_f$
are colored by colors from
$Y_f$
. So
If
$G-X$
has an
$L^{\phi _f}$
-coloring
$\theta $
, then
$\phi _f \cup \theta $
would be an L-coloring of G. Thus
$G-X$
is not
$L^{\phi _f}$
-colorable.
Lemma 5.1
$V_f-X_f$
contains at most
$ \lambda -1 $
singletons of G. Moreover, if
$V_f-X_f$
contains
$ \lambda -1\ge 1 $
singletons of G, then
$\ell =\lambda $
and the following hold:
-
(1) All f-classes have size 2 or 1, and there are exactly $\ell f$
-classes of size 2. -
(2) All the $\ell f$
-classes of size 2 are contained in
$X_f$
. -
(3) For each non-singleton part P of G, there is a singleton f-class $\{v\}\in X_f$
such that
$v \in P$
. -
(4) If f has exactly one badly colored vertex, then $|Y_f|\ge k+1$
.
Proof It follows from the definition of
$\phi _f$
that for each vertex v of
$ G-X$
,
$\{v\} \in X_f$
is a singleton f-class, and
$L(v) \subseteq Y_f$
. As
$|L^{\phi _f}(X) \cap Y_f| \le \ell $
,
If
$G_f-X_f$
contains
$ \ell $
singletons of G, then
By Noel–Reed–Wu theorem,
$ G-X$
is
$L^{\phi _f}$
-colorable, a contradiction.
So
$G_f-X_f$
contains at most
$ \ell -1$
singletons of G.
Assume
$G_f-X_f$
contains
$ \lambda -1 $
singletons of G. Since
$\ell \le \lambda $
, we have
$\ell =\lambda $
and hence each f-class has size at most 2, and there are exactly
$\ell f$
-classes of size 2, i.e., (1) holds. We shall prove that (2)–(4) hold.
(2): Assume to the contrary that there is an f-class of size
$2$
not in
$X_f$
. Then at most
$\ell -1 f$
-classes are colored by colors from
$Y_{\mathcal {S}}$
. Hence
As
$ G-X$
with list assignment
$L^{\phi _f}$
satisfy the condition of Noel–Reed–Wu theorem, and hence
$ G-X$
has an
$L^{\phi }$
-coloring, a contradiction.
(3): If (3) does not hold, then there is a non-singleton part P of G such that all vertices of P are colord, i.e., P is a non-singleton part of G contained in X, and hence
$\chi (G-X) \le k - \lambda = k -\ell $
. We still have
$ |V( G-X)|\le 2k+2-2\ell -(\lambda -1) \le 2(k-\ell )+1$
. Hence by Noel–Reed–Wu theorem,
$ G-X$
has an
$L^{\phi _f}$
-coloring, a contradiction.
(4): Assume
$v^*$
is the only badly colored vertex. Then
$\{v^*\}$
is an f-class of size 1 in
$X_f$
. This implies that
$|Y_f|\ge |L(v^*)| \ge k$
. Assume to the contrary that
$|Y_f|= k$
. This implies that for all singleton f-classes
$\{v\} \in X_f$
,
$L(v)=Y_f$
.
Assume
$f^{-1}(c) \in X_f$
is an f-class of size at least 2, and
$P_i$
is the part of G containing
$f^{-1}(c)$
. As the size of
$f^{-1}(c)$
is at least 2,
$P_i$
is not singleton-part and hence it follows from (3) that there is an f-class
$\{v\} \in X_f$
such that
$v \in P_i$
. Thus,
$L(v) = Y_f$
,
$c \in L(v)$
and we can color v with color c, and color
$v^*$
with
$f(v)$
. The resulting coloring is a pseudo L-coloring of G with no badly colored vertices, i.e., an L-coloring of G, a contradiction.
This completes the proof of Lemma 5.1.
Lemma 5.2 Assume
$\lambda \ge 2$
and G has at most
$\lambda -1$
singletons. Then
$G_f-X_f$
contains at most
$\lambda -2$
singletons of G.
Proof If G has at most
$\lambda -2$
singletons, then the conclusion is trivial. Assume G has exactly
$\lambda -1$
singletons (i.e.,
$p_1=\lambda -1$
), and assume to the contrary that all the
$\lambda -1$
singletons of G are contained in
$G_f-X_f$
. By (3) of Lemma 5.1, for each of the
$k-\lambda +1 2^+$
-parts P of G,
$X_f$
has a singleton f-class
$\{v\}$
with
$v \in P$
. By Lemma 5.1, we have
$\ell =\lambda $
. By (2) of Lemma 5.1, all the
$\ell f$
-classes of size 2 are contained in
$X_f$
. Thus
If a 2-part P of G is contained in
$ V(X_f)$
, then
$L(P)\subseteq Y_f$
. By Lemma 3.2,
This contradicts to the fact that
$|Y_f| < |C_L| = |V|-\lambda \le 2k$
.
Thus for each 2-part P of G,
$|P \cap V(G_f-X_f)|\ge 1.$
(Note that a 2-part has no common color in the lists of its vertices, so P is not an f-class.) Hence
As
$p_1=\lambda -1$
, it follows from (5.1) and (5.2) that
So
which implies that
$p_3^+ \ge p_1$
, in contrary to (4.7).
This completes the proof of Lemma 5.2.
6 Near acceptable colorings
We have shown in the previous section that the partition
$\mathcal {S}$
of
$V(G)$
induced by a pseudo-L-coloring of G has some nice properties. However, for the proof of Theorem 1.2, one more restriction need to be added to a pseudo-L-coloring. In this section, we define the concept of near acceptable L-coloring of G, and prove that the partition
$\mathcal {S}$
of G induced by a near acceptable L-coloring of G enables us to construct a proper L-coloring.
Definition 6.1 A color c is called frequent if one of the following holds:
-
(1) $|L^{-1}(c)| \ge k+2$
. -
(2) $|L^{-1}(c) \cap T| \ge \lambda $
. -
(3) $|T|=\lambda -1\ge 1$
and
$T \subseteq L^{-1}(c)$
.
Definition 6.2 A pseudo L-coloring f of G is near acceptable if each badly colored vertex is colored by a frequent color.
The concept of near acceptable L-coloring was first used in [Reference Noel, Reed and Wu17] for the proof of Noel–Reed–Wu theorem. For the proof of Theorem 1.2, as G has one more vertex, the definition of frequent colors is different from that in [Reference Noel, Reed and Wu17]. Thus the near acceptable L-coloring in this paper is different from the one in [Reference Noel, Reed and Wu17]. The difference makes it more difficult to find a near acceptable L-coloring of G. Nevertheless, we shall show that analog to [Reference Noel, Reed and Wu17], the existence of a near acceptable L-coloring of G implies the existence of an L-coloring of G.
Lemma 6.1 G has no near acceptable L-coloring.
Proof Assume to the contrary that f is a near acceptable L-coloring of G. Since
$|X_f|> |Y_f|$
, there is a color class
$f^{-1}(c^*)\in X_f$
with
$c^*\notin Y_f$
. Hence
$f^{-1}(c^*)=\{v^*\}$
is a badly colored singleton f-class.
Since
$f^{-1}(c^*)=\{v^*\}\in X_f$
, we have
$L(v^*) \subseteq Y_f$
, and hence
On the other hand,
$c^*\notin Y_f$
implies that for each
$f^{-1}(c) \in X_f$
, there exists
$v \in f^{-1}(c)$
, such that
$c^* \notin L(v)$
. Thus
So
$c^*$
is not a frequent color of Type (1).
By Lemma 5.1,
$V_f-X_f$
contains at most
$ \lambda -1 $
singletons of G. Hence
So
$c^*$
is not a frequent color of Type (2).
If
$|T|=\lambda -1\ge 1$
, then by Lemma 5.2,
$| L^{-1}(c^*) \cap T| \le |V(V_f-X_f) \cap T| \le \lambda -2$
. Hence
$T \not \subseteq L^{-1}(c^*)$
. So
$c^*$
is not a frequent color of Type (3).
Therefore,
$c^*$
is not frequent, a contradiction.
7 Upper bound on the number frequent colors
This section proves that there are at most
$k-1$
frequent colors. Assume to the contrary that there is a set F of k frequent colors. We will construct a near acceptable coloring f of G in the following three steps:
-
(1) Construct a partial L-coloring $f_1$
of G using colors from
$C_L-F$
, that colors as many vertices as possible, and subject to this, the colored vertices are distributed among the parts of G as evenly as possible. Let
$V_1$
be the set of vertices colored by
$f_1$
. -
(2) Order the parts of G as $P_1,P_2, \ldots , P_k$
so that
$|P_i -V_1| \ge |P_{i+1} - V_1|$
for
$i=1,2,\ldots , k-1$
. Color greedily in this order the vertices of
$P_i-V_1$
by a common permissible color from F, until this process cannot be carried out any more. This partial L-coloring will be denoted by
$f_2$
. Let
$V_2$
be the set of vertices colored by
$f_2$
. -
(3) Extend $f_1\cup f_2$
to a near acceptable L-coloring (for example, if for each remaining part
$P_i$
,
$P_i -V_1$
contains at most one vertex, then we arbitrarily color that vertex by a remaining color from F to obtain a near acceptable L-coloring of G).
The difficult part is to prove that
$f_1 \cup f_2$
can be extended to a near acceptable L-coloring. What we really proved is that if this cannot be done, then every part of G is a
$3^-$
-part, which is in contrary to Theorem 4.1.
In the proof, we often need to modify a partial L-coloring.
Definition 7.1 Assume f is a partial L-colorings of G. For distinct colors
$c_1, c_2, \ldots , c_t \in C_L$
, and distinct indices
$i_1, i_2, \ldots , i_t \in \{1,2,\ldots , k\}$
, we denote by
the partial L coloring of G obtained from f by the following operation:
-
• First, for $j=1,2,\ldots , t$
, uncolor vertices in
$f^{-1}(c_j)$
(it is allowed that
$f^{-1}(c_j)=\emptyset $
, i.e.,
$c_j$
is not used by f). -
• Second, for $j=1,2,\ldots , t$
, color vertices in
$L^{-1}(c_j) \cap P_{i_j} $
by color
$c_j$
.
Now we are ready to prove the following lemma.
Lemma 7.1 There are at most
$k-1$
frequent colors.
Proof Assume to the contrary that there is a set F of k frequent colors. A valid partial L-coloring f of G is a partial L-coloring of G using colors from
$C_L-F$
.
For a valid partial L-coloring f of G, for
$i=1,2,\ldots , k$
, let
be the set of colored vertices in
$P_i$
. Let
We choose a valid partial L-coloring
$f_1$
of G such that
is lexicographically maximum, i.e., the number of colored vertices
$\tau (f_1)$
is maximum, and subject to this,
$\tau _2(f) = \sum _{i=1}^k |S_{f_1,i}|^2$
is minimum, which means that the colored vertices are distributed among the parts of G as evenly as possible.
Let
$V_1 = f_1^{-1}(C_L-F) = \bigcup _{i=1}^k S_{f,i}$
be the set of vertices colored by
$f_1$
. By the maximality of
$\tau _1(f_1)$
,
$V_1$
must have used all the colors in
$C_L-F$
, and hence
$|C_L-F| \le |V_1|$
.
If
$|V-V_1| \le k$
, then let
$g:V-V_1\to F$
be an arbitrary injective mapping. The union
$f_1\cup g$
is a near acceptable L-coloring of G, and we are done. Thus we may assume that
For
$i=1,2,\ldots , k$
, let
For a color
$c \in C_L$
, let
be the number of vertices in
$R_{f_1,i}$
that can be colored by c, and
be the total number of vertices in
$R_{f_1,i}$
that can be colored by colors from
$C_L-F$
.
If
$c \in C_L-F$
, then
for otherwise,
$f_1(c \to P_i)$
is a valid partial L-coloring of G which colors more vertices than
$f_1$
, in contrary to the choice of
$f_1$
.
Definition 7.2 A color
$c \in C_L-F$
is said to be movable to
$P_i$
if
$R_i(c) = |f_1^{-1}(c)|$
.
Observation 7.2 The following facts will be used frequently in the argument below.
-
(1) If $c \in C_L-F$
is movable to
$P_i$
, then
$f_1(c \to P_i)$
is a valid partial L-coloring of G with
$\tau _1(f_1(c \to P_i) ) = \tau _1(f_1)$
. -
(2) $R_i(C_L-F) \le |V_1-P_i|$
, and if
$R_i(C_L-F) = |V_1-P_i|$
, then (P1) $$ \begin{align} \text{every color}\ c \in C_L-F\ \text{with}\ f_1^{-1}(c) \cap P_i = \emptyset\ \text{is movable to}\ P_i. \end{align} $$
-
(3) If $f_1^{-1}(c)$
is a singleton
$f_1$
-class, then c is movable to
$P_i$
if and only if
$c \in L(R_{f,i})$
. -
(4) For any choices of distinct colors $c_1,c_2, \ldots , c_t \in C_L$
and indices
$i_1, i_2, \ldots , i_t$
,
$f_1(c_1 \to P_{i_1}, c_2 \to P_{i_2}, \ldots , c_t \to P_{i_t})$
is a partial L-coloring of G.
Proof (1),(3), (4) are trivial.
(2): If
$c\in C_L-F$
and
$f^{-1}(c) \cap P_i \ne \emptyset $
, then
$R_i(c) = 0$
, for otherwise, we can color vertices in
$\{v \in R_{f_1, i}: c \in L(v)\}$
with color c. By the fact that
$R_i(c) \le |f^{-1}_1(c)|$
, we have
$R_i(c) \le |f_1^{-1}(c) - P_i|$
for any color
$c \in C_L-F$
. Hence
$R_i(C_L-F) = \sum _{c \in C_L-F}R_i(c) \le |V_1-P_i|$
, and equality holds only if
$R_i(c) = |f_1^{-1}(c)|$
for all
$c \in C_L-F$
with
$f_1^{-1}(c) \cap P_i = \emptyset $
.
Claim 7.3 If
$|P_i| = 2$
, then
$S_{f_1,i} \neq \emptyset $
.
Proof Assume to the contrary that
$P_i=\{u,v\}$
and
$S_{f_1,i}= \emptyset $
. By Lemma 3.2,
$L(u \wedge v) = \emptyset $
. Hence
$|C_L|\ge 2k$
and
$|V_1|\ge |C_L-F|\ge k$
. So there are at least
$k f_1$
-classes. As
$|V_1| \le k+1$
(see (7.1)), each
$f_1$
-class is a singleton, except at most one
$f_1$
-class is of size 2.
Since
$S_{f_1,i}= \emptyset $
, there is an index
$j_0$
such that
$|f_1(S_{f_1,j_0}))| \ge 2$
. Assume
$c_1,c_2 \in f_1(S_{f_1,j_0})$
. At least one of
$ f_1^{-1}(c_1), f_1^{-1}(c_2) $
is a singleton
$f_1$
-class.
If
$|C_L|=2k$
, then
$L(u \vee v)=C_L$
and by (3) of Observation 7.2, one of
$c_1,c_2$
, say
$c_1$
, is movable to
$P_i$
and
$f_1^{-1}(c_1)$
is a singleton
$f_1$
-class. If
$|C_L|=2k+1$
, then there are
$k+1 f_1$
-classes, and hence each
$f_1$
-class is a singleton. So both
$ f_1^{-1}(c_1), f_1^{-1}(c_2) $
are singleton
$f_1$
-classes, and at least one of
$c_1, c_2$
belongs to
$L(R_{f_1,i})$
and hence is movable to
$P_i$
.
Assume
$ f_1^{-1}(c_1)$
is a singleton
$f_1$
-class and
$c_1$
is movable to
$P_i$
.
Then
$\tau _1(f_1(c_1 \to P_i))=\tau _1(f_1)$
,
$\tau _2(f_1(c_1 \to P_i)) < \tau _2(f_1)$
. This is in contrary to our choice of
$f_1$
.
By a re-ordering, if needed, we assume that
In the second step, starting from
$i=1$
to k, we do the following: If there is a color
$c\in F$
such that
$c\in \bigcap _{v\in R_{f_1,i}}L(v)$
and c is not used by
$R_{f_1,j}$
for
$j < i$
, then we color
$R_{f_1,i}$
with c. The step terminates when such a color does not exist.
Assume the second step stopped at
$i_0+1$
, and hence
$R_{f_1,1}, \ldots , R_{f_1,i_0}$
are colored in the second step.
Note that in the ordering of
$R_{f_1,1}, R_{f_1,2}, \ldots , R_{f_1,k}$
, if some of the
$R_{f_1,j}$
’s has the same cardinality, then we can choose different ordering so that (R1) still holds. Also with a given ordering of
$R_{f_1,1}, R_{f_1,2}, \ldots , R_{f_1,k}$
, when we color all the vertices of
$R_{f_1,i}$
, there may be more than one choice of the colors. We assume that
We denote by
$f_2$
the coloring constructed in the second step, and by
$V_2$
the set of vertices colored in this step, and let
$V_3 = V -V_1 -V_2$
be the set of uncolored vertices after the second step. Let
$F_1$
be the frequent colors used in second step, and let
$F_2=F-F_1$
. So
$|F_1|=i_0$
and
$|F_2|=k-i_0$
. Note that it is possible that
${i_0}=0$
and
$V_2 =\emptyset $
.
If
$ |R_{f_1,{i_0}+1}| \le 1$
, then
$|V_3|\le k-{i_0}=|F_2|$
, and
$f_1\cup f_2$
can be extended to a near acceptable L-coloring of G by coloring
$V_3$
injectively by
$F_2$
, and we are done.
Therefore the following hold:
Observe that for each color
$c \in F_2$
,
and for each color
$c \in F_1$
,
Hence
and if the equality holds, then
Combining (7.2) with (7.3) and by (2) of Observation 7.2, we have
So
$|V_1|=k-{i_0}$
or
$|V_1|=k-{i_0}+1$
.
Case 1:
$|V_1|=k-{i_0}$
.
In this case,
So (P1) and (P2) holds for
$i_0+1$
. By Claim 7.3,
$|P_{{i_0}+1}|=|R_{f_1,{i_0}+1}|\ge 3$
. Hence
$|V_2|\ge 3{i_0}$
. This implies that
and hence
${i_0}\le 1$
.
Case 1.1:
$i_0=1$
.
In this case,
$|V_1|=k-1$
,
$|V_2|\ge 3$
and
$|V_3|\ge k$
(by (7.2), i.e.,
$|V_3|\ge k-i_0+1=k$
). Since
$|V|=2k+2$
, we conclude that
$|V_2|=|R_{f_1,1}|=3$
and
$|V_3|=k$
.
By (7.7),
$R_2(C_L-F)= |V_1|= k-1$
. This implies that
Hence there is a color
$c_1\in F$
such that
$R_2(C_L-F)(c_1) =|L^{-1}(c_1)\cap R_{f_1,2}|\ge 3= |R_{f_1,1}|\ge |R_{f_1,2}|$
. So
$c_1\in \bigcap _{v\in R_{f_1,2}}L(v)$
. On the other hand, by (7.7),
$P_2 = R_{f_1,2}$
, and by Lemma 3.2,
$ \bigcap _{v\in P_2}L(v) = \emptyset $
, a contradiction.
Case 1.2:
$i_0=0$
.
In this case,
Combining with
$i_0=0$
and (P2), for each color
$c \in F$
,
$R_1(c)=|R_{f_1,1}|-1$
.
Claim 7.4
$|P_1|=|R_{f_1,1}|=3$
and
$R_1(c) = 2$
for any color
$c \in F$
.
Proof If
$|R_{f_1,1}| \ge 4$
, then for any color
$c \in F$
,
$f_1(c \to P_1)$
can be extended to a near acceptable L-coloring of G by coloring the remaining
$k-1$
vertices of
$V_3$
injectively with the remaining
$k-1$
colors of F (note that
$|L^{-1}(c) \cap P_1|=|R_{f_1,1}|-1 \ge 3$
).
Thus
$|P_1|=|R_{f_1,1}|=3$
(cf. (7.7)). This implies that
$R_1(c) = 2$
for any color
$c \in F$
.
If there is a color
$c \in F$
such that
$R_2(c)\ge 2$
, then
$f_1$
can be extended to a near acceptable L-coloring of G by coloring a 2-subset
$U_1$
of of
$R_{f_1,2}$
with a color
$c \in \bigcap _{v \in U_1}L(v) \cap F$
, coloring a 2-subset
$U_2$
of
$R_{f_1,1}$
by a color from
$c' \in \bigcap _{v \in U_2}L(v) \cap (F-\{c\})$
, and coloring the remaining
$k-2$
vertices of
$V_3$
injectively with the remaining
$k-2$
colors of F.
Thus
This implies that
$|R_{f_1,2}| \le 2$
, for otherwise interchanging the roles of
$R_{f_1,1}$
and
$R_{f_1,2}$
, we would have
$R_2(c) =|R_{f_1,2}|-1\ge 2$
for all
$c \in F$
, in contrary to (7.9).
Claim 7.5
$|R_{f_1,i}|=1$
for
$i=2,3,\ldots , k$
.
Proof Assume to the contrary that
$|R_{f_1,2}|=2$
(as
$|R_{f_1,2}|\le 2$
), then by Observation 7.2,
$R_2(C_L-F)\le |V_1-P_2| =|V_1|-|S_{f_1,2}| = k-|S_{f_1,2}|$
and
Combining with (7.9), we have
$|S_{f_1,2}|=0$
and hence
$R_{f_1,2}=P_2$
, in contrary to Claim 7.3. By Claim 7.3,
$|S_{f_1,2}|\ge 1$
, in contrary to (7.9).
Therefore
$|R_{f_1,2}|=1$
and hence
$|R_{f_1,i}|=1$
for
$i=2,3,\ldots , k$
(note that
$|V_3|=k+2$
).
Claim 7.6
$|S_{f_1,j}|\le 2$
for
$j=2,3,\ldots , k$
.
Proof If
$|f_1(S_{f_1,j})| \ge 2$
for some j, say
$c_1, c_2\in f_1(S_{f_1,j})$
, then
$\tau _1(f_1(c_1 \to P_1)) = \tau _1(f_1) $
(as (P1) holds) and
$\tau _2(f_1(c \to P_1)) <\tau _2(f_1)$
, because
and
since
$|f_1(S_{f_1,j})| \ge 2$
. This is in contrary to our choice of
$f_1$
.
Hence for each
$j\in \{2,3,\ldots , k\}$
,
$|f_1(S_{f_1,j})| \le 1$
, and
$ |S_{f_1,j}| \le |f_1^{-1}(c_j)|$
for some
$c_j \in C_L-F$
. As (P1) holds,
$ |f_1^{-1}(c_j)| = R_1(C_L-F)(c_j) \le 2$
. So
$ |S_{f_1,j}| \le 2$
.
Combining with Claims 7.4, 7.5, and 7.6, we have
So each part of G is
$3^-$
-part, in contrary to Theorem 4.1.
Case 2:
$\mathbf {|V_1|=k-i_0+1}$
.
If
$P_{i_0+1}=R_{f_1,i_0+1}$
, then by Claim 7.3,
$ |R_{f_1,i_0+1}|\ge 3$
and
$|V_2|\ge 3i_0$
. By (7.2),
$|V_1|= |V|-|V_2|-|V_3| \le 2k+2 - 3i_0 - (k-i_0+1) = k-2i_0+1$
, and hence
$i_0=0$
. This implies that
By Observation 7.2,
$R_1(C_L-F)\le |V_1|=k+1$
, we conclude that
So there is a color
$c \in F$
such that
$R_1(c)\ge 2$
. We can extend
$f_1$
to a near acceptable L-coloring of G by coloring two vertices of
$R_{f_1,1}$
with c, and the remaining
$k-1$
vertices of
$V_3$
injectively with the remaining
$k-1$
colors of F.
Thus
$P_{i_0+1} \ne R_{f_1, i_0+1}$
, i.e.,
$S_{f_1, i_0+1} \ne \emptyset $
.
As
$S_{f_1, i_0+1} \ne \emptyset $
,
$|V_1 -P_{i_0+1}|=|V_1|-|S_{f_1,i_0+1}| < |V_1|$
and by (7.6), we have
So (P1) and (P2) holds for
$i_0+1$
.
Claim 7.7 For each
$1 \le i \le i_0+1$
,
$|R_{f_1,i}| = 2$
and for
$j \ge i_0+2$
,
$|R_{f_1,i}| \le 2$
.
Proof By (7.2), we have
$|V_2|\ge 2i_0$
,
$|V_3|\ge k-i_0+1$
. Since
$|V_1|+|V_2|+|V_3| = 2k+2$
, we conclude that
So
$\forall j\le i_0+1, \ |R_{f_1,j}|=2, \text { and } \forall j \ge i_0+2, \ |R_{f_1,j}| \le 2.$
Claim 7.8 For
$1 \le i \le k$
, if
$|R_{f_1,i}|=2$
, then
$|S_{f_1,i}|=1$
.
Proof By Claim 7.7,
$|R_{f_1,1}| = \ldots = |R_{f_1, i_0+1}|$
. As (P2) holds, there are
$i_0$
colors
$c \in F_1\subseteq F$
such that
$R_{i_0+1}(c)=|R_{f_1,i_0+1}|$
. Therefore, for any index j with
$|R_{f_1,j}|=2$
, if we re-order the parts so that
$R_{f_1,j}$
and
$R_{f_1, i_0+1}$
interchange positions (while the other parts stay at their position), (R1) and (R2) are satisfied. So the conclusions we have obtained for
$P_{i_0+1}$
hold for
$P_j$
. In particular, for any j with
$|R_{f_1,j}|=2$
, we have
$|S_{f_1,j}|=1$
.
Claim 7.9
$|S_{f_1,j}| \le 2$
for all j.
Proof As
$(P1)$
holds for
$i_0+1$
,
$|f_1^{-1}(c)|=R_{i_0+1}(c)\le |R_{f_1,i_0+1}|=2$
for any
$c\in C_L-F$
. If
$|S_{f_1,j}| \ge 3$
for some j, then there is a color
$c \in C_L-F$
for which the following holds:
-
• $|f_1^{-1}(c) \cap P_j| =1$
, or -
• $|S_{f_1,j}| \ge 4$
, and
$|f_1^{-1}(c) \cap P_j| =2$
.
Let
Then
$f^{\prime }_1$
is a valid partial L-coloring of G with
$\tau _1(f^{\prime }_1) = \tau _1(f_1)$
(as (P1) holds). By (7.11),
$|S_{f_1, i_0}|=1$
. Thus either
$|S_{f^{\prime }_1,j}| = |S_{f_1,j}|-1 \ge 2$
and
$|S_{f^{\prime }_1, i_0+1}|=2$
, or
$|S_{f^{\prime }_1,j}| = |S_{f_1,j}|-2 \ge 2$
and
$|S_{f^{\prime }_1, i_0+1}|=3$
. Hence
$\tau _2(f^{\prime }_1 )) < \tau _2(f_1)$
, in contrary to our choice of
$f_1$
.
It follows from Claims 7.8 and 7.9 that each part of G is
$3^-$
-part, in contrary to Theorem 4.1.
This completes the proof of Lemma 7.1.
8 Tighter upper bound for the number of frequent colors
In this section and the next section, we assume that
$(G,L)$
is a minimum counterexample to Theorem 1.2 with
$\sum _{v \in V(G)}|L(v)|$
maximum.
This section proves that there are at most
$k-p_1-1$
frequent colors. Assume to the contrary that there are
$k-p_1$
frequent colors. We shall construct another k-list assignment
$L'$
of G that has k frequent colors. By Lemma 7.1,
$(G,L')$
is not a counterexample to Theorem 1.2. Hence there is an
$L'$
-coloring f of G. Using this coloring f, we construct a near-acceptable L-coloring of G, which contradicts Lemma 6.1.
Let F be the set of frequent colors, and
$F' \subseteq F $
be the set of frequent colors of Type (1).
By Lemma 7.1, we may assume that
$|F| \le k-1$
. If
$\lambda =1$
, then for any
$v \in T$
, all colors in
$L(v)$
are frequent of Type (2), a contradiction (note that
$p_1 \ge 3$
, so
$T \ne \emptyset $
). Thus
$\lambda \ge 2$
.
Lemma 8.1
$\lambda \le p_1+1$
.
Proof For
$c\in C_L-F'$
, by definition,
$|L^{-1}(c)|\le k+1$
. By Lemma 3.2, for each
$c \in F'$
,
$|L^{-1}(c)|\le k+p_1+2$
. Therefore
Hence
As
$|F'| < k$
, we have
Since
$\lambda \ge 2$
, we have
$|C_L| \le 2k$
. Plug this into (8.2), we have
$\lambda \le p_1+2$
.
If
$\lambda =p_1+2$
, then
$|C_L|=|V| - \lambda = 2k+2 -(p_1+2) =2k-p_1\le 2k-3$
(as
$p_1\ge 3$
). This implies that G has no 2-part (if
$\{u,v\}$
is a 2-part of G, then
$L(u) \cap L(v) = \emptyset $
and hence
$|C_L| \ge 2k$
). By (4.7),
$2k-1 = |V|-3 \ge 3(k-p_1)+p_1$
. Hence
By (8.1),
Hence
$|F'|\ge k$
, a contradiction. Thus
$\lambda \le p_1+1$
.
Lemma 8.2
$F = \bigcap _{v \in T}L(v)$
.
Proof If
$p_1=\lambda -1$
, then each color in
$ \bigcap _{v \in T}L(v)$
is contained in at least
$\lambda -1$
singleton lists, and hence is a frequent color of Type (3).
If
$p_1\ge \lambda $
, then each color in
$ \bigcap _{v \in T}L(v)$
is contained in at least
$\lambda $
singleton lists, and hence is a frequent color of Type (2).
In any case,
On the other hand, assume there is a frequent color
$c \notin \bigcap _{v \in T}L(v)$
, say
$c \notin L(v)$
for some
$v \in T$
, then let
$L'$
be the list assignment of G defined as
$L'(x) = L(x)$
for
$x \ne v$
and
$L'(v) =L(v) \cup \{c\}$
. By our assumption that
$(G,L)$
is a minimum counterexample with
$\sum _{v \in V(G)}|L(v)|$
maximum, G and
$L'$
is not a counterexample to Theorem 1.2. So G has an
$L'$
-coloring f. But then f is a near acceptable L-coloring of G, in contrary to Lemma 6.1. Therefore
$F \subseteq \bigcap _{v \in T}L(v).$
Lemma 8.3 There are at most
$k-p_1-1$
frequent colors.
Proof Assume to the contrary that
$\{c_{p_1+1}, c_{p_1+2}, \ldots , c_k\}$
is a set of
$k-p_1$
frequent colors.
Assume
$T=\{v_1, v_2, \ldots , v_{p_1}\}$
. We choose
$p_1$
colors
$c_1, c_2, \ldots , c_{p_1}$
so that for
$i=1,2,\ldots , p_1$
,
As
$|L(v_i)| \ge k$
, the color
$c_i$
exists.
Let
$C'=\{c_1, c_2, \ldots , c_k\}$
and define
$L'$
as follows:
By Lemma 8.1,
$p_1\ge \lambda -1$
. If
$p_1\ge \lambda $
, then each color in
$C'$
is Type-2 frequent with respect to
$L'$
. If
$p_1=\lambda -1$
, then each color in
$C'$
is Type-3 frequent with respect to
$L'$
. By Lemma 7.1,
$(G, L')$
is not a minimum counterexample to Theorem 1.2. Since
$C_{L'} \subseteq C_L$
, we know that
$(G,L')$
is not a counterexample to Theorem 1.2. Hence G has an
$L'$
-coloring f.
Note that if
$v \notin T$
, then
$f(v) \in L(v)$
. We shall modify f to obtain a near acceptable L-coloring of G.
Let
$T'=\{v_i: 1 \le i \le p_1, c_i\in f(T)\}$
. As
$|T-T'|=|f(T)-\{c_1, c_2, \ldots , c_{p_1}\}|$
, there is a bijection
$g: T-T'\to f(T)-\{c_1, c_2, \ldots , c_{p_1}\}$
.
Let
$f':V\to C_L$
be defined as follows:
Then
$f'$
is a near acceptable L-coloring of G, in contradiction to Lemma 6.1.
9 Final contradiction
We shall find a subset X of T and a set
$F"$
of
$k-p_1$
colors so that for each
$c \in F"$
,
This would imply that all the
$k-p_1$
colors in
$F"$
are frequent (of Type (2)). This is in contrary to Lemma 7.1.
For any color
$c \in C_L-F$
,
$|L^{-1}(c)| \le k+1$
. Let
Lemma 9.1 There is a subset X of T such that
-
(1) $|X| \ge p_1-\lambda +1$
. -
(2) $|L(X)|\le k+b$
.
Moreover, if
$b=0$
or
$p_1=\lambda -1$
, then
$|X| \ge p_1-\lambda +2$
.
Proof Let
$c' \in C_L-F$
be a color with
$|L^{-1}(c')|=k+1-b$
. By Lemma 8.2, there is a vertex
$w \in T$
such that
$c' \notin L(w)$
. Define a list assignment
$L'$
as follows:
By the maximality of
$\sum _{v \in V(G)}|L(v)|$
, G has an
$L'$
-coloring f. We must have
$f(w) = c'$
and w is the only badly colored vertex, for otherwise f is a proper L-coloring of G.
Now f is a pseudo L-coloring of G. By Lemma 5.1, in the bipartite graph
$B_f$
,
$V_f$
has a subset
$X_f$
such that
$|X_f|> |Y_f|=|N_{B_f}(X_f)|$
, and
$V_f-X_f$
contains at most
$\lambda -1$
singletons of G.
It is easy to see that
$w\in X_f$
and
$c'\notin Y_f$
. Let
Then
$|X|=|T|-|(V_f-X_f)\cap T|\ge p_1-\lambda +1 $
and by Lemma 5.2, if
$p_1=\lambda -1$
, then
$|X|=|T|-|(V_f-X_f)\cap T|\ge p_1-\lambda +2 $
.
Since each f-class in
$X_f$
contains a vertex v for which
$c' \notin L(v)$
, we have
So
$|L(X)|\le k+b.$
It remains to prove that if
$b=0$
, i.e.,
$|L^{-1}(c')|=k+1$
, then
$|X| \ge p_1-\lambda +2$
.
Assume to the contrary that
$|L^{-1}(c')|=k+1$
and
$|X| = p_1-\lambda +1$
. By Lemma 5.1,
$|Y_f|\ge k+1$
and hence
$|X_f|\ge k+2$
, in contrary to
$|X_f|\le |V|-| L^{-1}(c')| = k+1$
.
This completes the proof of Lemma 9.1.
We order the colors in
$L(X)$
as
$c_1,c_2, \ldots , c_t$
, so that
where
$t=|L(X)|$
. Let
$F"=\{c_1, c_2, \ldots , c_{k-p_1}\}$
.
It suffices to show that
and hence each color
$c_i \in F"$
is a frequent of Type (2).
Let
$Z=\{c_{k-p_1},c_{k-p_1+1}, \ldots , c_t\}$
. For each
$v\in X$
,
$|L(v) \cap Z| \ge |L(v)| - (k-p_1-1) \ge p_1+1$
. Hence
By Lemma 9.1,
Plugging this into (9.1), we have
This implies that
For each
$c \in C_L-F$
,
$| L^{-1}(c)| \le k+1-b$
(by definition of b). By Lemma 3.2, for
$c \in F$
,
$| L^{-1}(c)| \le k+p_1+2$
. Hence
Plugging
$|C_L|=|V|-\lambda =2k+2-\lambda $
and
$|F|\le k-p_1-1$
into (9.3), we have
(Note that the coefficient of
$|F|$
in the right hand side of (9.3) is positive.)
This implies
If
$\lambda =2$
, then since
$p_1 \ge 3$
, by plugging
$|X|\ge p_1-\lambda +1$
(see Lemma 9.1) into (9.2), we have
Since
$|L^{-1}(c_{k-p_1}) \cap X|$
is an integer,
$|L^{-1}(c_{k-p_1}) \cap X|\ge 2 =\lambda $
and we are done.
Therefore
$\lambda \ge 3$
and
$|C_L| \le 2k-1$
. By Lemma 3.2, G has no 2-parts. By the same reason as (8.3), we have
Combining (8.1) with Lemma 8.3, together with
$p_1 \ge \frac {k+1}{2}$
, we have
Hence
Since
$\lambda $
is an integer,
Therefore
Plugging this into (9.5), we have
It follows from (9.6) that
$p_1 \ge 2\lambda -2$
.
If
$p_1\in \{2\lambda -2, 2\lambda -1\}$
, then
$b=0$
. This implies that
$|X|\ge p_1-\lambda +2$
.
It follows from (9.2) that
If
$p_1\ge 2\lambda $
, then
Hence
This completes the whole proof of Theorem 1.2.
This paper characterizes all non-k-choosable complete k-partite graphs G with
$2k+2$
vertices. If the number of vertices of G increases, and the chromatic number remains k, then the choice number of G may increase. It was proved in [Reference Noel, West, Wu and Zhu16] that k-chromatic graphs with
$n \ge 2k+1$
vertices have choice number at most
$\lceil \frac {n+k-1}{3} \rceil $
. It would be interesting to characterize graphs for which this upper bound on the choice number is sharp.
Acknowledgments
We thank the referee for a careful reading of the manuscript and for many valuable comments that improved the presentation of this paper.
