论文标题
关于平面图的灵活性弱
On Weak Flexibility in Planar Graphs
论文作者
论文摘要
最近，Dvo红，Norin和Postle引入了灵活性，作为图表上列表着色的扩展[JGT 19']。在这种新环境中，$ v（g）$的某个子集中的每个顶点$ v $都要求其颜色$ l（v）$中的一定颜色$ r（v）$。目标是找到满足许多（但不一定全部）请求的$ l $着色。 研究的主要问题是是否存在通用常数$ε> 0 $，以使某些图类别$ \ MATHCAL {C} $中的任何图形$ g $都满足请求的至少$ε$比例。更正式的是，对于$ k> 0 $，目标是证明，对于任何图形$ g \ in \ Mathcal {C} $ in Vertex set $ v $，每个顶点的任何列表分配$ l $的尺寸$ k $，每个$ r \ r \ subseteq v $ and repleass unespect vector $（v） $ l $ - 颜色的$ g $满足至少$ε| r | $请求。如果这是真的，则$ \ MATHCAL {C} $称为$ε$ - 对于尺寸$ k $的列表。 Choi等。 [arxiv 20']引入了弱灵活性的概念，其中$ r = v $。我们通过引入一种处理弱灵活性的工具来进一步开发此方向。我们通过证明存在$ε（b）> 0 $的每个正整数$ b $来证明这种新工具，以便没有$ k_4，c_5，c_5，c_6，c_6，c_7，b_b $的平面图等级是薄弱顶点）。我们还表明，没有$ K_4，C_5，C_6，C_7，B_5 $的平面图类别是$ε$ - 适用于尺寸$ 4 $的列表。结果很紧，因为这些图形类甚至无法3色。
Recently, Dvořák, Norin, and Postle introduced flexibility as an extension of list coloring on graphs [JGT 19']. In this new setting, each vertex $v$ in some subset of $V(G)$ has a request for a certain color $r(v)$ in its list of colors $L(v)$. The goal is to find an $L$ coloring satisfying many, but not necessarily all, of the requests. The main studied question is whether there exists a universal constant $ε>0$ such that any graph $G$ in some graph class $\mathcal{C}$ satisfies at least $ε$ proportion of the requests. More formally, for $k > 0$ the goal is to prove that for any graph $G \in \mathcal{C}$ on vertex set $V$, with any list assignment $L$ of size $k$ for each vertex, and for every $R \subseteq V$ and a request vector $(r(v): v\in R, ~r(v) \in L(v))$, there exists an $L$-coloring of $G$ satisfying at least $ε|R|$ requests. If this is true, then $\mathcal{C}$ is called $ε$-flexible for lists of size $k$. Choi et al. [arXiv 20'] introduced the notion of weak flexibility, where $R = V$. We further develop this direction by introducing a tool to handle weak flexibility. We demonstrate this new tool by showing that for every positive integer $b$ there exists $ε(b)>0$ so that the class of planar graphs without $K_4, C_5 , C_6 , C_7, B_b$ is weakly $ε(b)$-flexible for lists of size $4$ (here $K_n$, $C_n$ and $B_n$ are the complete graph, a cycle, and a book on $n$ vertices, respectively). We also show that the class of planar graphs without $K_4, C_5 , C_6 , C_7, B_5$ is $ε$-flexible for lists of size $4$. The results are tight as these graph classes are not even 3-colorable.
