论文标题
具有特殊退化条件的图表中的柔性列表着色
Flexible List Colorings in Graphs with Special Degeneracy Conditions
论文作者
论文摘要
对于给定的$ \ varepsilon> 0 $，我们说图$ g $是$ \ varepsilon $ - 额外的$ k $ -k $ - choos-choosable，如果有以下内容：对于任何任务$ l $ l $的颜色$ l $ $ k $ on $ v（g）上的$ k $ in $ v（g）$，如果在列表中请求$ r $ r $ r $ r $通过一些$ l $颜色。我们考虑在具有某些退化条件的几个图形类别中的灵活可选性问题。 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].特别是，我们表明，对于任何$δ\ geq 3 $，任何最大程度$δ$的图都不是同构成$ k_ {δ+1} $ is $ \ frac {1} {1} {6Δ} $ - 灵活地$δ$ - $ choosable。我们的$ \ frac {1} {6Δ} $的分数在最佳的不变因素之内。我们还表明，树宽$ 2 $的图是$ \ frac {1} {3} $ - 灵活地，$ 3 $ - choosable，回答Choi等人的问题[Arxiv 2020]，我们为列表分配提供了条件，通过哪些Tree-Width $ K $ k $ k $ k $是$ \ frac $ \ frac {1} $ choos $ choos $ choos $ choos $（k+1）我们还表明，TreeDepth $ k $的图是$ \ frac {1} {k} $ - 灵活地$ k $ -choosable。最后，我们引入了一个灵活的退化概念，可以增强灵活性的可选性，除了众所周知的例外类别外，最大程度$δ$的3个相互连接的非规范图是灵活的$ $ $（δ-1）$ - 退化。
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.
