Flexible List Coloring of Graphs With Maximum Average Degree Less Than 3

Abstract

In the flexible list coloring problem, we consider a graph and a color list assignment on , as well as a subset for which each has a preferred color . Our goal is to find a proper ‐coloring of such that for at least vertices . We say that is ‐flexibly ‐choosable if for every ‐size list assignment on and every subset of vertices with coloring preferences, has a proper ‐coloring that satisfies an proportion of these coloring preferences. Dvořák, Norin, and Postle [Journal of Graph Theory, 2019] asked whether every ‐degenerate graph is ‐flexibly ‐choosable for some constant . In this paper, we prove that there exists a constant such that every graph with maximum average degree less than 3 is ‐flexibly 3‐choosable, which gives a large class of 2‐degenerate graphs which are ‐flexibly ‐choosable. In particular, our results imply a theorem of Dvořák, Masařík, Musílek, and Pangrác [Journal of Graph Theory, 2020] stating that every planar graph of girth 6 is ‐flexibly 3‐choosable for some constant . To prove our result, we generalize the existing reducible subgraph framework traditionally used for flexible list coloring to allow reducible subgraphs of arbitrarily large order.