List-Coloring and Chromatic-Choosability - A Dynamic Survey

Nandana K Vasudevan 1 , K Somasundaram 1 and N Narayanan 2 · 2026

Read List-Coloring and Chromatic-Choosability - A Dynamic Survey by Nandana K Vasudevan 1 , K Somasundaram 1 and N Narayanan 2 (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2606-31702.txt.

Description

Vasudevan, Somasundaram and Narayanan survey list-coloring, a generalization of graph coloring where each vertex carries its own list of allowed colors. A graph is chromatic-choosable when its list chromatic number equals its ordinary chromatic number. The topic began with work by Vizing and by Erdős, Rubin and Taylor in the 1970s, and the last full survey dates to 2001.

Coverage spans graph classes where equality is known and classes where a real gap appears. Embedded graphs, perfect graphs, bipartite and multipartite graphs, claw-free graphs, line graphs and graph products all receive treatment. The authors also review the main proof methods and several variants of list-coloring. Open conjectures about which classes are chromatic-choosable organize much of the discussion.

Catalog record

CREATORNandana K Vasudevan 1 , K Somasundaram 1 and N Narayanan 2
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE71 KB
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2606.31702

Browse the full library · About the Tower of Babel