Choosability in bounded sequential list coloring
share
The list coloring problem is a variation of the classical vertex coloring problem, extensively studied in recent years, where each vertex has a restricted list of allowed colors, and having some variations as the (γ,μ)-coloring, where the color lists have sequential values with known lower and upper bounds. This work discusses the choosability property, that consists in determining the least number k for which it has a proper list coloring no matter how one assigns a list of k colors to each vertex. This is a Π_2^P-complete problem, however, we show that k-(γ,μ)-choosability is an NP-problem due to its relation with the k-coloring of a graph and application of methods of proof in choosability for some classes of graphs, such as complete bipartite graph, which is 3 -choosable, but 2 -(γ,μ)-choosable.
READ FULL TEXT