2025/09/28 by Bowdoin, Michael C., Chi, Yanghong, Ellington, Christian B. +4
#05C15 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2509.24013
Chromatic-choosablility is a notion of fundamental importance in list coloring. A graph G is chromatic-choosable when its chromatic number, χ(G), is equal to its list chromatic number χℓ(G). Flexible list coloring was introduced by Dvořák, Norin, and Postle in 2019 in order to address a situation in list coloring where we still seek a proper list coloring, but each vertex may have a preferred color assigned to it, and for those vertices we wish to color as many of them with their preferred colors as possible. In flexible list coloring, the list flexibility number of G, denoted χℓ flex(G), serves as the natural analogue of χℓ(G). In 2002, Ohba famously showed that for any graph G, there exists an N ∈ ℕ such that χ(Kp \vee G) = χℓ(Kp \vee G) whenever p ≥ N. Since χ(G) ≤ χℓ(G) ≤ χℓ flex(G), it is natural to ask whether this result holds if χℓ is replaced with χℓ flex. In this paper we not only show that this result doesn't hold in general if χℓ is replaced with χℓ flex, but we also give a characterization of the graphs for which it does hold.