Choosability in bounded sequential list coloring

MaRDI QIDQ6311815zbMATH OpenFDO

Authors Simone Gama, Rosiane de Freitas, Mario Jun. Salvatierra

Publication date 30 December 2018

Abstract: 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 $(gamma,mu)$-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 $P{i}_2^P$-complete problem, however, we show that $k$-$(gamma,mu)$-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$-$(gamma,mu)$-choosable.

This page was built for publication: Choosability in bounded sequential list coloring

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6311815)