




















For a given $\varepsilon > 0$, we say that a graph $G$ is $\varepsilon$-flexibly $k$-choosable if the following holds: for any assignment $L$ of color lists of size $k$ on $V(G)$, if a preferred color from a list is requested at any set $R$ of vertices, then at least $\varepsilon |R|$ of these requests are satisfied by some $L$-coloring. We consider the question of flexible choosability in several graph classes with certain degeneracy conditions. We characterize the graphs of maximum degree $Δ$ that are $\varepsilon$-flexibly $Δ$-choosable for some $\varepsilon = \varepsilon(Δ) > 0$, which answers a question of Dvořák, Norin, and Postle [List coloring with requests, JGT 2019]. In particular, we show that for any $Δ\geq 3$, any graph of maximum degree $Δ$ that is not isomorphic to $K_{Δ+1}$ is $\frac{1}{6Δ}$-flexibly $Δ$-choosable. Our fraction of $\frac{1}{6 Δ}$ is within a constant factor of being the best possible. We also show that graphs of treewidth $2$ are $\frac{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 $\frac{1}{k+1}$-flexibly $(k+1)$-choosable. We show furthermore that graphs of treedepth $k$ are $\frac{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.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。