论文标题
$ p $以$ p $的色彩的两个下限
Two lower bounds for $p$-centered colorings
论文作者
论文摘要
给定图形$ g $和一个整数$ p $，一个颜色$ f：v（g）\ to \ mathbb {n} $ is \ emph {$ p $ - 式}，如果每个连接的子级$ h $ of $ g $，$ f $，$ f $ co $ a $ f $都比$ h $ h $ h $ h $ h $ h $ h $ h $ h。 $ p $的色彩的概念在稀疏图理论中起着核心作用。在本说明中，我们在$ p $以$ p $的着色中所需的颜色数量显示了两个下限。 首先，我们考虑其浅层未成年人的单调类别的平均程度在半径上或等效（由于dvoDemank和Norin的结果），承认强烈的sublinear分离器。我们构建了这样的类，以至于$ p $的着色需要多种颜色的$ p $中的超级多项式。这与Pilipczuk和Siebertz的最新结果相反，Pilipczuk和Siebertz在图形的特殊情况下建立了一个多项式上限，不包括固定的未成年人。 其次，我们考虑最高度$δ$的图。 DęBSKI，FELSNER，MITEK和SCRöder最近证明，这些图具有$ o（δ^{2-1/p} p）$ colors的$ p $中心颜色。我们表明，有一些最大度$δ$的图需要$ω（δ^{2-1/p} p \ ln^{ - 1/p}δ）$颜色在任何$ p $中心的着色中，从而匹配它们的上限与对数因子。
Given a graph $G$ and an integer $p$, a coloring $f : V(G) \to \mathbb{N}$ is \emph{$p$-centered} if for every connected subgraph $H$ of $G$, either $f$ uses more than $p$ colors on $H$ or there is a color that appears exactly once in $H$. The notion of $p$-centered colorings plays a central role in the theory of sparse graphs. In this note we show two lower bounds on the number of colors required in a $p$-centered coloring. First, we consider monotone classes of graphs whose shallow minors have average degree bounded polynomially in the radius, or equivalently (by a result of Dvořák and Norin), admitting strongly sublinear separators. We construct such a class such that $p$-centered colorings require a number of colors super-polynomial in $p$. This is in contrast with a recent result of Pilipczuk and Siebertz, who established a polynomial upper bound in the special case of graphs excluding a fixed minor. Second, we consider graphs of maximum degree $Δ$. Dębski, Felsner, Micek, and Schröder recently proved that these graphs have $p$-centered colorings with $O(Δ^{2-1/p} p)$ colors. We show that there are graphs of maximum degree $Δ$ that require $Ω(Δ^{2-1/p} p \ln^{-1/p}Δ)$ colors in any $p$-centered coloring, thus matching their upper bound up to a logarithmic factor.
