论文标题
DP颜色函数与色多项式（II）
DP color functions versus chromatic polynomials (II)
论文作者
论文摘要
对于任何连接的图形$ g $，令$ p（g，m）$和$ p_ {dp}（g，m）$分别表示$ g $的色度多项式和DP颜色函数。众所周知，$ p_ {dp}（g，m）\ le p（g，m）$均为每个正整数$ m $保留。令$ dp_ \ $（分别$ dp _ <$）是一组图形$ g $，存在整数$ m $，以至于$ p_ {dp}（g，m）= p（g，m）$（spec. $ p_ $ p_ {dp}（dp}（g，m）<p（g，m）<p（g，m）$）确定集合$ dp_ \ of $和$ dp _ <$是研究DP颜色功能的关键问题。对于任何边缘集合$ g $的$ e_0 $ g $，令$ \ ell_g（e_0）$是$ g $中最短周期$ c $的长度，以便每当存在这样的周期时，$ | e（c）\ cap e_0 | $是奇怪的，$ \ ell_g（e_0）= \ fiffty $否则。写$ \ ell_g（e_0）$为$ \ ell_g（e）$，如果$ e_0 = \ {e \} $。 在本文中，我们证明，如果$ g $具有跨越的树$ t $，则$ \ ell_g（e）$对于e（g）\ setminus e（t）$的每个$ e \都是奇怪的，则可以将$ e（g）\ setminus e（t）中的边缘标记为$ e_1，e_1，e_2 e_2 e _2，e__ $ cdots，e___ el el。 \ ell_g（e_ {i+1}）$ for ahl $ 1 \ le i \ le i \ le q-1 $，每个边缘$ e_i $都包含在一个周期$ c_i $ of length $ \ ell_g（e_i）$带有$ e（c_i）\ e（c_i）\ subseteq e（c_i）\ subseteq e（t） $ dp _ {\ lot} $。作为该结论的直接应用，所有平面近三角仪和具有至少三个部分集的完整多部分图属于$ dp _ {\ lot of} $。我们还表明，如果$ e^*$是$ g $的边缘集，这样$ \ ell_ {g}（e^*）$均为均匀而$ e^*$满足某些条件，则$ g $属于$ dp _ <$。特别是，如果$ \ ell_g（e^*）= 4 $，其中$ e^*$是$ g $的两个不相关顶点子集之间的一组边缘，则$ g $属于$ dp _ <$。这两个结果都扩展了[DP颜色函数与色度多项式的已知结果，$ proped \ in \ applied \ Mathematics $ 134（2022），第102301条]。
For any connected graph $G$, let $P(G,m)$ and $P_{DP}(G,m)$ denote the chromatic polynomial and DP color function of $G$, respectively. It is known that $P_{DP}(G,m)\le P(G,m)$ holds for every positive integer $m$. Let $DP_\approx$ (resp. $DP_<$) be the set of graphs $G$ for which there exists an integer $M$ such that $P_{DP}(G,m)=P(G,m)$ (resp. $P_{DP}(G,m)<P(G,m)$) holds for all integers $m \ge M$. Determining the sets $DP_\approx$ and $DP_<$ is a key problem on the study of the DP color function. For any edge set $E_0$ of $G$, let $\ell_G(E_0)$ be the length of a shortest cycle $C$ in $G$ such that $|E(C)\cap E_0|$ is odd whenever such a cycle exists, and $\ell_G(E_0)=\infty$ otherwise. Write $\ell_G(E_0)$ as $\ell_G(e)$ if $E_0=\{e\}$. In this paper, we prove that if $G$ has a spanning tree $T$ such that $\ell_G(e)$ is odd for each $e\in E(G)\setminus E(T)$, the edges in $E(G)\setminus E(T)$ can be labeled as $e_1,e_2,\cdots, e_q$ with $\ell_G(e_i)\le \ell_G(e_{i+1})$ for all $1\le i\le q-1$ and each edge $e_i$ is contained in a cycle $C_i$ of length $\ell_G(e_i)$ with $E(C_i)\subseteq E(T)\cup \{e_j: 1\le j\le i\}$, then $G$ is a graph in $DP_{\approx}$. As a direct application of this conclusion, all plane near-triangulations and complete multipartite graphs with at least three partite sets belong to $DP_{\approx}$. We also show that if $E^*$ is an edge set of $G$ such that $\ell_{G}(E^*)$ is even and $E^*$ satisfies certain conditions, then $G$ belongs to $DP_<$. In particular, if $\ell_G(E^*)=4$, where $E^*$ is a set of edges between two disjoint vertex subsets of $G$, then $G$ belongs to $DP_<$. Both results extend known ones in [DP color functions versus chromatic polynomials, $Advances\ in\ Applied\ Mathematics$ 134 (2022), article 102301].
