5choosable

5choosable refers to a property in graph theory related to list coloring. A graph G is k-choosable if, for every assignment L that gives each vertex v a list L(v) of available colors with |L(v)| ≥ k, there exists a proper coloring c of G where c(v) ∈ L(v) for all vertices v. When k = 5, G is called 5choosable. This strengthens ordinary colorability, since a 5-choosable graph must be 5-colorable, but the existence of a global coloring from arbitrary 5-element lists is a stricter requirement.

A central topic in the area is choosability, or list colorability, and the corresponding choice number ch(G), the smallest k for which G is k-choosable. Known results include that complete graphs K_n are n-choosable, and that the concept generalizes many classical coloring questions.

A landmark result is Thomassen’s theorem (1994): every planar graph is 5-choosable. This shows that the list version of five-coloring holds for all planar graphs, and it establishes a tight boundary for planarity, since there are planar graphs that are not 4-choosable (Voigt, early 1990s). Thus 5-choosability is the correct threshold for planar graphs.

In general, determining whether a given graph is k-choosable is computationally difficult; for fixed k ≥ 3, the problem is known to be NP-hard in general. The study of 5choosable graphs intersects with topics such as planar graph theory, list coloring, and the broader theory of choosability in graphs.