List Coloring - Computing Choosability and (a,b)-choosability

Computing Choosability and (a,b)-choosability

Two algorithmic problems have been considered in the literature:

1. k-choosability: decide whether a given graph is k-choosable for a given k, and
2. (j,k)-choosability: decide whether a given graph is f-choosable for a given function .

It is known that k-choosability in bipartite graphs is -complete for any k ≥ 3, and the same applies for 4-choosability in planar graphs, 3-choosability in planar triangle-free graphs, and (2,3)-choosability in bipartite planar graphs. For P₅-free graphs, that is, graphs excluding a 5-vertex path graph, k-choosability is fixed-parameter tractable.

It is possible to test whether a graph is 2-choosable in linear time by repeatedly deleting vertices of degree zero or one until reaching the 2-core of the graph, after which no more such deletions are possible. The initial graph is 2-choosable if and only if its 2-core is either an even cycle or a theta graph formed by three paths with shared endpoints, with two paths of length two and the third path having any even length.