On (k, t)-choosability of graphs.
Wongsakorn Charoenpanitseri, Narong Punnim, Chariya Uiyyasathian · Ars Combinatoria · 2011
A k-list assignment L of a graph G is a mapping which assigns to each vertex v of G a set L(v) of size k. A (k,t)-list assignment of G is a k-list assignment with | ⋃ v∈V (G) L(v)| = t. An L-coloring φ of G is a proper coloring of G such that φ(v) is chosen from L(v) for every vertex v. A graph G is Lcolorable if G has an L-coloring. When the parameter t is not of special interest, we simply say k-list assignment. Particularly, if L is a (k, k)-list assignment of G, then any L-coloring is called a k-coloring for 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 any number t then G is k-choosable and the smallest number k satisfying this properties is called the list chromatic number of G denoted by χl(G). The list coloring problem is first studied by Vizing[6] and by Erdos, Rubin and Taylor[2]. In [2], the authors give a characterization of 2-choosable graphs. There is no literature giving a characterization of k-choosable graphs for k ≥ 3. The k-choosability of graphs is revealed only for some specific classes of graphs. For example, Thomassen[5] proves that every planar graph is 5-choosable while some planar graphs are 3-choosable. (See [4],[8],[7],[3],[9] and [10].) Ganjari et al. [1] use (k, t)-choosability of graphs to characterize uniquely 2-list colorable graphs. When k ≥ χl(G), a graph G is always (k, t)-choosable. In this paper, we focus on any integer k such that k < χl(G). For an n-vertex graph G, we find the value t in terms of n and k such that G is (k, t)-choosable. Our main study includes the following results. For fixed numbers n, k and t, every n-vertex graph is (k, t)-choosable if and only if t ≥ kn − k2 + 1. In case k ≤ t ≤ kn − k2, every n-vertex graph containing Kk+1 is not (k, t)choosable. Furthermore, every Kk+1-free n-vertex graph is (k, t)-choosable if and only if t ≥ kn−k2−2k. If k ≤ t ≤ kn−k2−2k+1, an n-vertex graph