Flexible List Coloring of Graphs With Maximum Average Degree Less Than 3
Journal of Graph Theory · 15.07.2026
DOI: 10.1002/jgt.70095 ↗Kurz gefasst
Fachartikel in der Zeitschrift Journal of Graph Theory, online erschienen am 15.07.2026. Verfasst von Richard Bi und 1 weiteren Autor:innen. Die Arbeit nennt 18 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: National Science Foundation.
Abstract (Originalsprache)
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.
Förderung
- National Science Foundation
Zitieren
APA
Bi, R., & Bradshaw, P. (2026). Flexible List Coloring of Graphs With Maximum Average Degree Less Than 3. Journal of Graph Theory. https://doi.org/10.1002/jgt.70095
Vancouver
Bi R, Bradshaw P. Flexible List Coloring of Graphs With Maximum Average Degree Less Than 3. Journal of Graph Theory. 2026. doi:10.1002/jgt.70095
BibTeX
@article{Bi2026,
author = {Bi, Richard and Bradshaw, Peter},
title = {Flexible List Coloring of Graphs With Maximum Average Degree Less Than 3},
journal = {Journal of Graph Theory},
year = {2026},
doi = {10.1002/jgt.70095}
}
EUVIMED