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
A landmark result is Thomassen’s theorem: every planar graph is 5-choosable. This implies planar graphs are
Deciding k-choosability is computationally challenging; for fixed k ≥ 3, determining whether a given graph is k-choosable