论文标题
调色板的稀疏超过$（δ+1）$顶点着色
Palette Sparsification Beyond $(Δ+1)$ Vertex Coloring
论文作者
论文摘要
最近的一个调色板稀疏定理，陈，陈和卡纳[Soda'19]指出，在每个$ n $ n $ vertex graph $ g $中，带有最高度$δ$的$ g $，对$ o（\ log {n}）$ colors a $δ+1 $肯定可以从$δ+1 $中独立于$ g $ g $ g $ go $ g $。除了是其自身独立兴趣的组合陈述外，该定理还显示出各种应用在$（δ+1）$颜色的算法上的各种应用，以大量的计算模型（例如流媒体或sublinearipe算法）上的不同计算模型。 在本文中，我们进一步研究了调色板的稀疏问题： *我们证明，对于$（1+ \ varepsilon）δ$着色，仅采样$ o _ {\ varepsilon}（\ sqrt {\ sqrt {\ log {n}}）$ pertex $ pertex $ colors是足够且必要的，即可从采样颜色中获得适当的着色。 *一个天然的图形家族，具有$ O（\fracΔ{\lnδ}）$ colorable的$ o（\fracδ{\lnδ}）$ colorable的天然图。我们证明，每个顶点的取样$ O（δ^γ + \ sqrt {\ log {n}}）$颜色是足够且需要获得适当的$o_γ（\fracδ{\lnδ}）$的三角形图形的颜色。 *我们表明，抽样$ o _ {\ varepsilon}（\ log {n}）$颜色每个顶点的颜色足以适合任何图形的适当颜色，每当每个顶点都从$（1+ \ varepsilon）列表中取样时，任何概率都很高，甚至只有$ deg（v）$ deg（v） $ \ {1，\ ldots，deg（v）+1 \} $。 与以前的工作类似，我们的新调色板稀疏结果自然会导致许多新的和/或改进的算法，用于在不同模型中的顶点着色，包括流媒体和sublrinear-time算法。
A recent palette sparsification theorem of Assadi, Chen, and Khanna [SODA'19] states that in every $n$-vertex graph $G$ with maximum degree $Δ$, sampling $O(\log{n})$ colors per each vertex independently from $Δ+1$ colors almost certainly allows for proper coloring of $G$ from the sampled colors. Besides being a combinatorial statement of its own independent interest, this theorem was shown to have various applications to design of algorithms for $(Δ+1)$ coloring in different models of computation on massive graphs such as streaming or sublinear-time algorithms. In this paper, we further study palette sparsification problems: * We prove that for $(1+\varepsilon) Δ$ coloring, sampling only $O_{\varepsilon}(\sqrt{\log{n}})$ colors per vertex is sufficient and necessary to obtain a proper coloring from the sampled colors. * A natural family of graphs with chromatic number much smaller than $(Δ+1)$ are triangle-free graphs which are $O(\fracΔ{\lnΔ})$ colorable. We prove that sampling $O(Δ^γ + \sqrt{\log{n}})$ colors per vertex is sufficient and necessary to obtain a proper $O_γ(\fracΔ{\lnΔ})$ coloring of triangle-free graphs. * We show that sampling $O_{\varepsilon}(\log{n})$ colors per vertex is sufficient for proper coloring of any graph with high probability whenever each vertex is sampling from a list of $(1+\varepsilon) \cdot deg(v)$ arbitrary colors, or even only $deg(v)+1$ colors when the lists are the sets $\{1,\ldots,deg(v)+1\}$. Similar to previous work, our new palette sparsification results naturally lead to a host of new and/or improved algorithms for vertex coloring in different models including streaming and sublinear-time algorithms.
