kchoosable

K-choosable, or k-choosable, is a concept in graph theory describing a strength of colorability under vertex-specific constraints. Given a graph G = (V,E), a list assignment L assigns to each vertex v a set L(v) of allowed colors. An L-coloring is a proper vertex coloring c: V → colors such that c(v) ∈ L(v) for every v and c(u) ≠ c(v) whenever uv ∈ E. The graph G is called k-choosable if for every assignment L with |L(v)| ≥ k for all vertices v, there exists an L-coloring of G. The L-coloring must pick a color for each vertex from its list, respecting adjacency.

The list chromatic number, χ_l(G), is the smallest k for which G is k-choosable; equivalently, the minimum k such that for every list assignment with |L(v)| ≥ k, G has an L-coloring. In general, χ_l(G) ≥ χ(G), where χ(G) is the ordinary chromatic number. That is, the list chromatic number never falls below the ordinary chromatic number, and in general it can be strictly larger.

Notable results and scope: list coloring and k-choosability generalize ordinary graph coloring and have been studied across graph families. A landmark result is Thomassen’s theorem that every planar graph is 5-choosable. It is known that planar graphs are not all 4-choosable, illustrating that the list version can require more colors than the standard chromatic number. The field includes a range of results for other graph classes and for various fixed k.

Computationally, determining whether a graph is k-choosable (i.e., whether χ_l(G) ≤ k) is generally difficult; for fixed k ≥ 3, the decision problem is NP-complete in many settings. Related topics include list coloring, the list chromatic number, and connections to chromatic number and planar graph theory.