kchoosability

K-choosability is a concept in graph theory describing how a graph behaves under list colorings. A graph G is called k-choosable if, for every assignment L that to each vertex v assigns a list L(v) of colors with |L(v)| = k, there exists a proper vertex coloring c such that c(v) ∈ L(v) for all vertices v. In other words, G can be colored from any collection of k available colors at each vertex. This generalizes ordinary graph coloring: a k-choosable graph is in particular k-colorable when all vertices share the same k colors.

The smallest k with this property is called the choice number, ch(G). In general, ch(G) ≥ χ(G), the usual chromatic number, and equality need not hold. For example, complete graphs K_n have ch(K_n) = n, while many graph families satisfy ch(G) = χ(G). A classical positive case is bipartite graphs, which are 2-choosable. For cycles, ch(C_n) = 2 if n is even and 3 if n is odd.

A landmark result is Thomassen’s theorem: every planar graph is 5-choosable. This implies planar graphs are 5-colorable, while some planar graphs are not 4-choosable. There exist graphs in general where the list chromatic number exceeds the ordinary chromatic number, illustrating that choosability is a stronger notion in some cases.

Deciding k-choosability is computationally challenging; for fixed k ≥ 3, determining whether a given graph is k-choosable is NP-complete in general. K-choosability remains a central topic in the study of list coloring, with connections to chromatic number, planar graphs, and extremal set theory.