2026-08-07T22:32:00Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:13375 2026-05-27T13:01:49Z ddc:004 open_access

Flexible List Colorings in Graphs with Special Degeneracy Conditions Bradshaw, Peter Masařík, Tomáš Stacho, Ladislav Flexibility List Coloring Choosability Degeneracy For a given ε > 0, we say that a graph G is ε-flexibly k-choosable if the following holds: for any assignment L of lists of size k on V(G), if a preferred color is requested at any set R of vertices, then at least ε |R| of these requests are satisfied by some L-coloring. We consider flexible list colorings in several graph classes with certain degeneracy conditions. We characterize the graphs of maximum degree Δ that are ε-flexibly Δ-choosable for some ε = ε(Δ) > 0, which answers a question of Dvořák, Norin, and Postle [List coloring with requests, JGT 2019]. We also show that graphs of treewidth 2 are 1/3-flexibly 3-choosable, answering a question of Choi et al. [arXiv 2020], and we give conditions for list assignments by which graphs of treewidth k are 1/(k+1)-flexibly (k+1)-choosable. We show furthermore that graphs of treedepth k are 1/k-flexibly k-choosable. Finally, we introduce a notion of flexible degeneracy, which strengthens flexible choosability, and we show that apart from a well-understood class of exceptions, 3-connected non-regular graphs of maximum degree Δ are flexibly (Δ - 1)-degenerate. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Peter Bradshaw and Tomáš Masařík and Ladislav Stacho 2020 Is Part Of LIPIcs, Volume 181, 31st International Symposium on Algorithms and Computation (ISAAC 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2020.31 urn:nbn:de:0030-drops-133750 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2020.31 eng https://creativecommons.org/licenses/by/3.0/legalcode