2016/01/08 by Marc Demange, Demange, Marc, D. de Werra +1
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.1601.01768
openalex publication_date 2016/01/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A graph is ℓ-choosable if, for any choice of lists of ℓ colors for each vertex, there is a list coloring, which is a coloring where each vertex receives a color from its list. We study complexity issues of choosability of graphs when the number k of colors is limited. We get results which differ surprisingly from the usual case where k is implicit and which extend known results for the usual case. We also exhibit some classes of graphs (defined by structural properties of their blocks) which are choosable.