论文标题
关于DP颜色功能的两个问题的答案
Answers to Two Questions on the DP Color Function
论文作者
论文摘要
DP颜色是列表着色的概括，该列表是由Dvočhkand Postle在2015年推出的。图形的色多项式是自20世纪初期以来一直在研究的一个概念。图$ g $的色度多项式表示为$ p（g，m）$，等于$ g $的适当$ m $颜色的数量。 2019年，考尔（Kaul）和穆德（Mudrock）引入了用于DP色的色度多项式的类似物。具体来说，图$ g $的DP颜色函数表示为$ p_ {dp}（g，m）$。 Kaul和Mudrock提出的两个基本问题是：（1）对于任何图形$ g $带有$ n $ vertices，是否是$ p（g，m）-p_ {dp}（g，m）= o（m^{n-3}）$ as $ m \ rightArrow \ rightArrow \ rightarrow \ infty $？ （2）对于每个图$ g $，是否存在$ p，n \ in \ mathbb {n} $，以至于$ p_ {dp}（k_p \ vee g，m）= p（k_p \ vee g，m）$，每当$ m \ m \ geq n $吗？我们表明，这两个问题的答案是肯定的。实际上，即使我们需要$ p = 1 $，我们也向（2）显示答案是肯定的。
DP-coloring is a generalization of list coloring that was introduced in 2015 by Dvořák and Postle. The chromatic polynomial of a graph is a notion that has been extensively studied since the early 20th century. The chromatic polynomial of graph $G$ is denoted $P(G,m)$, and it is equal to the number of proper $m$-colorings of $G$. In 2019, Kaul and Mudrock introduced an analogue of the chromatic polynomial for DP-coloring; specifically, the DP color function of graph $G$ is denoted $P_{DP}(G,m)$. Two fundamental questions posed by Kaul and Mudrock are: (1) For any graph $G$ with $n$ vertices, is it the case that $P(G,m)-P_{DP}(G,m) = O(m^{n-3})$ as $m \rightarrow \infty$? and (2) For every graph $G$, does there exist $p,N \in \mathbb{N}$ such that $P_{DP}(K_p \vee G, m) = P(K_p \vee G, m)$ whenever $m \geq N$? We show that the answer to both these questions is yes. In fact, we show the answer to (2) is yes even if we require $p=1$.
