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
| CREATOR | Nandana K Vasudevan 1 , K Somasundaram 1 and N Narayanan 2 |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 71 KB |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2606.31702