# On(k,kn-k2-2k-1)-Choosability of n-Vertex Graphs

Authors: Wongsakorn Charoenpanitseri
Journal: International Journal of Mathematics and Mathematical Sciences
 (2015)

---

## Abstract

A(k,t)-list assignment L of a graph G is a mapping which assigns a set of size k to each vertex v of G  and |⋃v∈V(G)‍L(v)|=t. A graph G is (k,t)-choosable if G has a proper coloring f such that f(v)∈L(v) for each (k,t)-list assignment L. In 2011, Charoenpanitseri et al. gave a characterization of (k,t)-choosability of n-vertex graphs when t≥kn-k2-2k+1 and left open problems when t≤kn-k2-2k. Recently, Ruksasakchai and Nakprasit obtain the results when t=kn-k2-2k. In this paper, we extend the results to case t=kn-k2-2k-1.


---

## Body

## 1. Introduction

A graphG is called k-colorable if every vertex of G can be labeled by at most k colors and every adjacent vertex receives distinct colors. The smallest number t such that G is t-colorable is called thechromatic number of G, denoted by χ(G). A k-list assignmentL of a graph G is a function which assigns a set of size k to each vertex v of G. A (k,t)-list assignment of a graph is a k-list assignment with ⋃v∈VG‍Lv=t. Given a list assignment L, a proper coloring f of G is an L-coloring of G if f(v) is chosen from L(v) for each vertex v of G. A graph G is L-colorable if G has an L-coloring. Particularly, if L is a k,k-list assignment of G, then any L-coloring of G is a k-coloring of G. A graph G is k,t-choosable if G is L-colorable for every k,t-list assignment L. If a graph G is k,t-choosable for each positive number t then G is called k-choosable and the smallest number k satisfying this property is called thelist chromatic number of G denoted by chG.List coloring is a well-known problem in the field of graph theory. It was first studied by Vizing [1] and by Erdös et al. [2]. They gave a characterization of 2-choosable graphs. For k≥3, there is no characterization of k-choosable graphs. There are only results for some classes of graphs. For example, all planar graphs are 5-choosable, while some planar graphs are 3-choosable. (See [3–9].) In order to simplify the problem, (k,t)-choosability is defined. It is a partial problem of k-choosability. Instead of proving that a graph can always be colored for entire k-list assignments, we prove the graph can be colored for k-list assignments that have exactly t colors. In 2011, (k,t)-choosability of graphs was explored in [10]. They proved the following theorem.Theorem 1 (see [10]).
For ann-vertex graph G, if t≥kn-k2+1, then G is (k,t)-choosable.Moreover, they showed that the bound is best possible by proving ift≤kn-k2, then an n-vertex graph containing Kk+1 is not (k,t)-choosable. Furthermore, they keep investigating the (k,t)-choosability to obtain another interesting theorem.Theorem 2 (see [10]).
Letk≥3. A Kk+1-free graph with n vertices is (k,t)-choosable for t≥kn-k2-2k+1.Again, they showed that the bound is best possible forKk+1-free graphs with n vertices by proving an n-vertex graph containing C5∨Kk-2 is not (k,t)-choosable for t≤kn-k2-2k. In conclusion, they gave a characterization of (k,t)-choosability of n-vertex graphs when t≥kn-k2-2k+1.In 2013, Ruksasakchai and Nakprasit gave a characterization of(k,kn-k2-2k)-choosability of n-vertex graphs as shown in the following theorem.Theorem 3 (see [11]).
LetG be a graph with n vertices and k≥3. If G does not contain Kk+1 and C5∨Kk-2, then G is (k,t)-choosable for t=kn-k2-2k.Results on(2,t)-choosability of n-vertex graphs are almost completed by [12, 13]. Here, we focus on k≥3. We will prove that if an n-vertex graph G does not contain Kk+1 and C5∨Kk-2, then G is (k,t)-choosable for t=kn-k2-2k-1.


## 2. Preliminaries

Throughout the paper,G denotes a simple, undirected, finite, connected graph; V(G) and E(G) are the vertex set and the edge set of G. For X⊆V(G), G-X is the graph obtained from deleting all vertices of X from G. In case X={v}, we write G-v instead of G-{v}. Thesubgraph induced byX, denoted by G[X], is the graph obtained from deleting all vertices of V(G) outside X. The notation d(v) stands for the degree of v in G. For a subgraph H of G, dH(v) stands for the degree of v in H.LetS⊆V(G). If L is a list assignment of G, we let L|S denote L restricted to S and L(S) denote ⋃v∈S‍L(v). For a color set A, let L-A be the new list assignment obtained from L by deleting all colors in A from L(v) for each v∈V(G). When A has only one color a, we write L-a instead of L-{a}.Example 4.
The cycleCn is (2,t)-choosable unless n is odd and t=2.Note that a graphG is (2,2)-choosable if and only if G is 2-colorable. Hence, Cn is (2,2)-choosable if and only if n is even. It remains to show that all of the cycles are (2,t)-choosable for t≥3.Lett≥3 and L be a (2,t)-list assignment of Cn. Thus there are two adjacent vertices v1,vn∈V(G) such that L(v1)≠L(vn). Let v2,v3,…,vn-1 be remaining vertices along the cycle Cn, where vi is adjacent to vi+1 for i=1,2,…,n-1. First we assign v1 a color c in L(v1) which is not in L(vn) and then we assign vertex v2 a color in L(v2) different from c and so on. This algorithm guarantees that each pair of adjacent vertices receives distinct colors.Theorem5 is a powerful tool when combined to Lemma 6. Everyone uses both of them to obtain a result on (k,t)-choosability of graphs.Theorem 5 (see [14]).
LetL be a list assignment of a graph G and let S⊆V(G) be a maximal nonempty subset such that LS<S. If G[S] is LS-colorable, then G is L-colorable.Lemma 6 (see [10]).
LetA1,A2,…,An be k-sets and J⊆{1,2,…,n}. If ⋃i=1n‍Ai≥p, then ⋃i∈J‍Ai≥p-n-Jk.The following statements appear in [10, 11]. They use the tools to obtain characterizations of (k,t)-choosability of n-vertex graphs. We also need the tools, as well.Lemma 7 (see [10]).
LetG be an n-vertex graph. If k≥n-2 and G is Kk+1-free, then G is (k,t)-choosable for any positive integer k.Lemma 8 (see [10]).
If ak+3-vertex graph is Kk+1-free, then it is k,t-choosable for t≥k+1.Lemma 9 (see [11]).
LetG be an n-vertex graph, where n≥6. If G does not contain Kn-2 and C5∨Kn-5, then G is (n-3)-colorable.Lemma 10 (see [11]).
LetG be a graph in Figure 1. If each list has size 2 exactly two lists of size 3 and |L(x4)|=2 or |L(x5)|=2, then G is L-colorable.Figure 1
The graph for Lemma10.Lemma 11 (see [11]).
LetG be a graph with 7 vertices and χ(G)=4. If G does not contain K4 and C5∨K1, then δ(G)≥3 and Δ(G)=4.Corollary 12 (see [11]).
IfG is a 7-vertex graph having no C5∨K1 and K4, then G is (3,6)-choosable.Recently, Ohba’s conjecture is proved by Noel as shown in Theorem13.Theorem 13 (see [15]).
If|V(G)|≤2χ(G)+1, then ch(G)=χ(G).The theorem is powerful because several interesting results can be obtained; for example, Corollaries14 and 15.Corollary 14.
LetG be an n-vertex graph with n≤7. If G is 3-colorable, then G is 3-choosable.Proof.
LetG be an n-vertex graph with n≤7. Assume that G is 3-colorable. Then χ(G)≤3. Then we add some edges to G to obtain a graph H such that χ(H)=3. Since VH≤7=2χ(H)+1, we obtain that chH=χH=3 by Theorem 13. Hence G is 3-choosable because G is a subgraph of H.Corollary 15.
LetG be an n-vertex graph with n≤9. If G is 4-colorable, then G is 4-choosable.Proof.
LetG be an n-vertex graph with n≤9. Assume that G is 4-colorable. Then χ(G)≤4. Then we add some edges to G to obtain a graph H such that χ(H)=4. Since |V(H)|≤9=2χ(H)+1, we obtain that ch(H)=χ(H)=4 by Theorem 13. Hence G is 4-choosable because G is a subgraph of H.Finally, we need one more theorem and one more lemma to prove our main results.Theorem 16 (see [16]).
IfG is a graph other than odd cycle and complete graph, then χ(G)≤Δ(G).Lemma 17 (see [11, 17]).
LetG be a graph with δ(G)≥3 and Δ(G)=4. If G has no K4 and C5∨K1, then G must be one of the 7 graphs in Figure 2.Figure 2
The 7-vertex graph with chromatic number4 and having no K4 and C5∨K1.


## 3. Main Results

In this section, the main result is in Theorem24. In order to prove the main result, we need to prove Theorems 19 and 23. Lemma 18 is established for Theorem 19 while Lemmas 20, 21, and 22 are established for Theorem 23.Lemma 18.
LetG be an 8-vertex graph with Δ(G)=5. If G has no K5 and C5∨K2, then G is 4-colorable.Proof.
LetG be an 8-vertex graph with Δ(G)=5. Assume that G has no K5 and C5∨K2.
If there is a vertexv such that d(v)≤3, then G-v is 4-colorable by Lemma 9; hence, G is 4-colorable, as well. Suppose that δ(G)≥4. Let v1 be a vertex with d(v1)=5 of G and let v2 be a vertex which is not adjacent to v1. Notice that d(v2) is 4 or 5.
Case 1 (G-v1-v2 contains C5∨K1). Under the condition Δ(G)=5, G-v1-v2 must be C5∨K1. Then G must be a subgraph of the graph shown in Figure 3. According to the figure, G and its subgraphs are 4-colorable.
Case 2 (G-v1-v2 contains K4). Let V(K4)={u1,u2,u3,u4}, H=G-{u1,u2,u3,u4}, and V(H)={v1,v2,w1,w2}.
Case 2.1 (d(v2)=5). Notice that H has at most 5 edges because H has 4 vertices and v1,v2 are not adjacent. Then dH(v1)+dH(v2)+dH(w1)+dH(w2)≤10. However, d(v1)=d(v2)=5 and d(w1),d(w2)≥4. Then d(v1)+d(v2)+d(w1)+d(w2)≥18. Hence, there are at least 8 edges between H and K4. Since dK4(ui)=3 and d(ui)≤5 for i=1,2,3,4, there are at most 8 edges between K4 and H.
Hence, there are exactly8 edges between K4 and H. Moreover, we obtain that H has exactly 5 edges, d(w1)=d(w2)=4, and d(u1)=d(u2)=d(u3)=d(u4)=5. Furthermore, each of w1,w2 is adjacent to exactly one vertex in V(K4).
Ifw1 and w2 are adjacent to different vertices in V(K4), then G must be the left graph in Figure 4. If w1 and w2 are adjacent to the same vertex in V(K4), then G must be the right graph in Figure 4. According to the figure, G is 4-colorable.
Case 2.2 (d(v2)=4). Notice that H has at most 5 edges because H has 4 vertices and v1,v2 are not adjacent. Then dH(v1)+dH(v2)+dH(w1)+dH(w2)≤10. However, d(v1)=5, d(v2)=4, and d(w1),d(w2)≥4. Then d(v1)+d(v2)+d(w1)+d(w2)≥17. Hence, there are at least 7 edges between H and K4.
SinceG does not contain K5, v1 is not adjacent to at least one vertex from K4, for example, u4. If d(u4)=5, then the proof is done by Case 2.1 because v1 and u1 are nonadjacent vertices with degree 5. Suppose that d(u4)=4. Since dK4(u1)=dK4(u2)=dK4(u3)=dK4(u4)=3 and d(ui)≤5 for i=1,2,3 and d(u4)=4 there are at most 7 edges between K4 and H.
Hence, there are exactly7 edges between K4 and H. Moreover, we obtain that H has exactly 5 edges, d(w1)=d(w2)=4 and d(u1)=d(u2)=d(u3)=5, and d(u4)=4. Furthermore, each of w1,w2 is adjacent to exactly one vertex in V(K4).
Ifw1 and w2 are adjacent to the same vertex in V(K4), then G must be the left graph in Figure 5. If w1 and w2 are adjacent to different vertices in V(K4), then G must be the middle graph or the right graph in Figure 5. According to the figure, G is 4-colorable.
Case 3 (G-v1-v2 contains neither K4 nor C5∨K1). By Lemma 9, G-v1-v2 is 3-colorable. Hence, all vertices from G-v1-v2 are labeled by 3 colors and v1,v2 are labeled by the fourth color. Therefore, G is 4-colorable.Figure 3
Case 1.Figure 4
Case 2.1.Figure 5
Case 2.2.Theorem 19.
IfG is an 8-vertex graph having no C5∨K2 and K5, then G is (4,7)-choosable.Proof.
Assume thatG is an 8-vertex graph having no C5∨K2 and K5. Then for every vertex v, G[N(v)] have no C5∨K1 and K4.
Case 1 (Δ(G)≤4). Then G is 4-colorable by Theorem 16. Hence, G is 4-choosable by Corollary 15.
Case 2 (Δ(G)=5). Then G is 4-colorable by Lemma 18. Hence, G is 4-choosable by Corollary 15.
Case 3 (Δ(G)=6). Let v be a vertex with d(v)=6 and w is the vertex which is not adjacent to v. Since |L(v)|=|L(w)|=4 and |L(V(G))|=7, L(v) and L(w) have a common color, for example, c. Hence, we label v and w by color c.
By Lemma9, G-u-v is 3-colorable because it has no C5∨K1 and K4. By Corollary 14, G-u-v is 3-choosable. That is, we can label the remaining vertices.
Case 4 (Δ(G)=7). Let v be a vertex with d(v)=7.
Case 4.1 (L(v)-L(V(G-v))≠∅). Then we can label v in order to obtain that each of the remaining 7 vertices still has 4 available colors. Since G-v has no C5∨K1 and K4, it is 4-colorable by Lemma 9. Then, it is 4-choosable by Corollary 15. That is, we can label the remaining vertices.
Case 4.2 (L(v)-L(V(G-v))=∅). Then we label v in order to obtain that each of the remaining seven vertices has at least 3 available colors and the number of the remaining colors is 7. According to Corollary 12, G-v is (3,6)-choosable. That is, we can label the remaining vertices.Lemma 20.
K
2,2
,
2 is L-colorable if |L(V(K2,2,2))|=4 and each list has size 3 except for one list of size 2.Proof.
LetX={x1,x2}, Y={y1,y2}, and Z={z1,z2} be partite sets of K2,2,2. Let L be a list assignment of K2,2,2 such that LVK2,2,2=4 and each list has size 3 except for one list of size 2. Without loss of generality, suppose that Lx1=2 and Lv=3 for the remaining 5 vertices. Since LVK2,2,2=4, there is a color c∈L(x1)∩L(x2). Then we label x1 and x2 by color c. Hence, each of the remaining 4 vertices has 2 available colors. Since C4 is 2-choosable, the remaining vertices can be labeled.Lemma 21.
G
5 is (3,5)-choosable.Proof.
LetL be a (3,5)-list assignment of G5. Since LVG5=5, we obtain that Lx1∪Lx2∪Lx3∪Lx4∪Lx5≥4 or Lx1∪Lx2∪Lx3∪Lx6∪Lx7≥4. Without loss of generality, suppose that Lx1∪Lx2∪Lx3∪Lx4∪Lx5≥4.
Since|L(x6)|=|L(x7)|=3 but |L(V(G5))|=5, there is a color c∈L(x6)∩L(x7). Then x6 and x7 are labeled by color c. Let L′=L-c be the list assignment of G-x6-x7. Since L′xi≥2 for i=1,2,3,4,5 and ⋃x∈VG-x6-x7‍L′x≥3, G-x6-x7 is L′-colorable by Example 4.Lemma 22.
G
7 is (3,5)-choosable.Proof.
Notice thatxi is not adjacent to xj if and only if i-j≡±1 mod 7. Let L be a (3,5)-list assignment of G7.
Case 1. There is a color c that appears in exactly 1 list. Without loss of generality, suppose c∈L(x1) but c∈L(v) for the remaining vertices v. Then we label x1 by color c. Each of the remaining six vertices has 3 available colors. Since G7-x1 does not contain K4 or C5∨K1, it is 3-colorable by Lemma 9. Hence, G7-x1 is 3-choosable by Corollary 14. That is, the remaining vertices can be labeled.
Case 2. There is a color c that appears in exactly 2 lists. Without loss of generality, we may prove only 3 subcases because xi is not adjacent to xj if and only if i-j≡±1 mod 7.
Case 2.1 (c∈L(x1)∩L(x2)). Then we label x1 and x2 by color c. Hence, G-x1-x2 is 3-colorable by Lemma 9. Consequently, it is 3-choosable by Corollary 14.
Case 2.2 (c∈L(x1)∩L(x3)). Then we label x1 by color c. Lemma 20 confirms that the remaining 6 vertices can be labeled.
Case 2.3 (c∈L(x1)∩L(x4)). Then we label x1 by color c. Again, Lemma 20 confirms that the remaining six vertices can be labeled.
Case 3. There is a color c that appears in exactly 4, 5, or 6 lists. According to the fact that xi is not adjacent to xj if and only if i-j≡±1 mod 7, we may prove only the following cases.
Ifc appears in exactly 4 lists, we suppose that c∈L(x1)∩L(x2)∩L(x3)∩L(x4) or c∈L(x1)∩L(x2)∩L(x3)∩L(x5) or c∈L(x1)∩L(x2)∩L(x4)∩L(x5) or c∈L(x1)∩L(x2)∩L(x4)∩L(x6). Then we label x1 and x2 by color c and Lemma 10 confirms that the remaining five vertices can be labeled.
Ifc appears in exactly 5 lists, we suppose that c∈L(x1)∩L(x2)∩L(x3)∩L(x4)∩L(x5) or c∈L(x1)∩L(x2)∩L(x3)∩L(x4)∩L(x6) or c∈L(x1)∩L(x2)∩L(x3)∩L(x5)∩L(x6). Again, we label x1 and x2 by color c and Lemma 10 confirms that the remaining five vertices can be labeled.
Ifc appears in exactly 6 lists, we suppose that c∈L(x1)∩L(x2)∩L(x3)∩L(x4)∩L(x6)∩L(x7). Similarly, we label x1 and x2 by color c and Lemma 10 confirms that the remaining five vertices can be labeled.
Case 4. Each color appears in exactly 3 or 7 lists. Let x and y be the number that appears in exactly 3 or 7 lists, respectively. Then x+y=5 and 3x+7y=21. There are no integer solutions for this system. Hence, this case is impossible.Theorem 23.
IfG is a 7-vertex graph having no C5∨K1 and K4, then G is (3,5)-choosable.Proof.
Assume thatG is a 7-vertex graph having no C5∨K1 and K4. Let L be a (3,5)-list assignment of G. According to Lemma 9, G is 4-colorable. Then χ(G)≤4. If χ(G)≤3, we apply Corollary 14. Hence, G is 3-choosable. Otherwise, suppose that χ(G)=4. By Lemma 11, we obtain that δ(G)≥3 and Δ(G)=4. By Lemma 17, G must be one of the seven graphs in Figure 2. By Lemma 21, G1, G2, G4, and G5 are (3,5)-choosable. By Lemma 22, G3, G6, and G7 are (3,5)-choosable.Theorem 24.
Letk≥3. If an n-vertex graph G does not contain Kk+1 and C5∨Kk-2, then G is (k,t)-choosable for t=kn-k2-2k-1.Proof.
LetG be a graph with n vertices and k≥3. Assume that G does not contain Kk+1 and C5∨Kk-2.
LetL be a (k,t)-list assignment such that t=kn-k2-2k-1. To apply Theorem 5, let S⊆V(G) such that |L(S)|<|S|. We need to prove that G[S] is L|S-colorable.
By Lemma6, |L(S)|≥t-(n-|S|)k=(kn-k2-2k-1)-(kn-|S|k)=|S|k-k2-2k-1. Then |S|>|L(S)|≥|S|k-k2-2k-1. It follows that |S|<k+3+4/k-1.
Case 1 (|S|≤k+2). Then G[S] is L|S-colorable by Lemma 7.
Case 2 (|S|=k+3). Then G[S] is L|S-colorable by Lemmas 8 and 9.
Case 3 (|S|≥k+4). Then k+4≤|S|<k+3+4/k-1. Hence, k=3 or k=4.
Case 3.1 (k=3). Then 3+4≤|S|<3+3+4/3-1. Consequently, |S|=7. Since |S|>|L(S)|≥|S|k-k2-2k-1, we obtain that |L(S)|≥5. If |L(S)|=6, then G[S] is L|S-colorable by Corollary 12. If |L(S)|=5, then G[S] is L|S-colorable by Theorem 23.
Case 3.2 (k=4). Then 4+4≤|S|<4+3+4/4-1. Consequently, |S|=8. Since |S|>|L(S)|≥|S|k-k2-2k-1, we obtain that |L(S)|=7. By Theorem 19, G[S] is L|S-colorable.


## 4. Open Problem

Thanks to [10, 11], a characterization of (k,t)-choosability of n-vertex graphs when k≥3 and t≥kn-k2-2k is obtained. According to [13], a (2,t)-choosability of n-vertex graphs when t≥2n-8 is obtained. In this paper, we give a characterization of (k,t)-choosability of n-vertex graphs when k≥3 and t=kn-k2-2k-1.Conjecture 25.
Letk≥3. If an n-vertex graph has no Kk+1 and Kk+1∨C5∨Kk-2, then it is (k,t)-choosable of t=kn-k2-2k-2.



---

*Source: 690517-2015-05-12.xml*