论文标题
灵活的列表着色：最大化满足请求的数量
Flexible list colorings: Maximizing the number of requests satisfied
论文作者
论文摘要
灵活列表着色是由Dvočák，Norin和Postle在2019年推出的。假设$ 0 \ 0 \ leqε\ leq 1 $，$ g $，$ g $是一张图，$ l $是$ g $的列表任务，$ r $是一个非空地$ d \ d \ subseteq v（g）$ r（$ r（v）$ r（v）$ n d（v）称为$ l $）。如果存在适当的$ l $ f $ $ g $的$ f $ f $ f $ f $ f（v）= r（v）= r（v）$至少$ε| d | d | $ d $ in $ d $，则三重$（g，l，r）$是$ε$ - 可满足的。我们说$ g $是$（k，ε）$ - 如果$（g，l'，r'）$是$ε$ - s usfimible，则$ l'$是$ g $的$ k $ - $ g $，而$ r'$是$ l'$的请求。 Dvo红等人表明。如果$ d+1 $是Prime，则$ G $是$ d $ -De-de-de-de-de-de-de-de-de-de-de-defemage，$ r $是$ g $的要求，$ g $，$ 1 $ $ 1 $，然后是$（g，l，r）$是$ 1 $ -STOSSISLIASE，只要$ l $是$（d+1）$ - 分配。在本文中，我们将此结果扩展到所有$ d $ for Bipartite $ d $ -Depegenate图。 关于灵活列表着色的文献倾向于表明，对于固定的图$ g $和$ k \ in \ mathbb {n} $，存在$ε> 0 $，因此$ g $是$ g $（k，ε）$ - 灵活，但自然可以尝试找到最大的$ $ g $ g $ $ g $ $ g $ $（k，k，k，β，ε）$ flex-- flex-- flex-- flex。在这种情况下，我们通过显示$ d $ -DECENATER图为$（D+2，1/2^{D+1}）$ - 灵活来提高Dvo红等人的结果。为了追求图形为$（k，ε）$的最大$ε$ - 灵活，我们观察到，图$ g $不是$（k，ε）$ - 对于任何$ k $而言，仅当$ε> 1/ρ（g）$，$ q $，其中$ρ（g）$是$ g $的$ g $，我们列出了$ g $ k $ n smimical k $ $ g $是$（k，1/ρ（g））$ - 灵活。我们研究列表灵活性号码，列表色号，列表包装编号和图形脱落之间的关系和连接。
Flexible list coloring was introduced by Dvořák, Norin, and Postle in 2019. Suppose $0 \leq ε\leq 1$, $G$ is a graph, $L$ is a list assignment for $G$, and $r$ is a function with non-empty domain $D\subseteq V(G)$ such that $r(v) \in L(v)$ for each $v \in D$ ($r$ is called a request of $L$). The triple $(G,L,r)$ is $ε$-satisfiable if there exists a proper $L$-coloring $f$ of $G$ such that $f(v) = r(v)$ for at least $ε|D|$ vertices in $D$. We say $G$ is $(k, ε)$-flexible if $(G,L',r')$ is $ε$-satisfiable whenever $L'$ is a $k$-assignment for $G$ and $r'$ is a request of $L'$. It was shown by Dvořák et al. that if $d+1$ is prime, $G$ is a $d$-degenerate graph, and $r$ is a request for $G$ with domain of size $1$, then $(G,L,r)$ is $1$-satisfiable whenever $L$ is a $(d+1)$-assignment. In this paper, we extend this result to all $d$ for bipartite $d$-degenerate graphs. The literature on flexible list coloring tends to focus on showing that for a fixed graph $G$ and $k \in \mathbb{N}$ there exists an $ε> 0$ such that $G$ is $(k, ε)$-flexible, but it is natural to try to find the largest possible $ε$ for which $G$ is $(k,ε)$-flexible. In this vein, we improve a result of Dvořák et al., by showing $d$-degenerate graphs are $(d+2, 1/2^{d+1})$-flexible. In pursuit of the largest $ε$ for which a graph is $(k,ε)$-flexible, we observe that a graph $G$ is not $(k, ε)$-flexible for any $k$ if and only if $ε> 1/ ρ(G)$, where $ρ(G)$ is the Hall ratio of $G$, and we initiate the study of the list flexibility number of a graph $G$, which is the smallest $k$ such that $G$ is $(k,1/ ρ(G))$-flexible. We study relationships and connections between the list flexibility number, list chromatic number, list packing number, and degeneracy of a graph.
