EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

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

Richard Bi, Peter Bradshaw

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →