论文标题
组合的组合和dp颜色图
Combinatorial Nullstellensatz and DP-coloring of Graphs
论文作者
论文摘要
我们启动研究将组合无效的nullstellensatz应用于图形的DP色彩，尽管众所周知，Alon-Tarsi定理并不适用于DP颜色。我们定义了良好的主要订单封面的概念，这使我们能够将组合无效的nullstellensatz应用于DP颜色。我们将这些工具应用于某些两部分图和独特3色图的锥体的DP色。我们还将Akbari，Mirrokni和Sadjad（2006）的结果扩展到了DP颜色的上下文。我们为图$ g $建立了足够的代数条件，以满足$χ_{dp}（g）\ leq 3 $，我们完全确定了所有周期的DP-Chromation数量正方形。
We initiate the study of applying the Combinatorial Nullstellensatz to the DP-coloring of graphs even though, as is well-known, the Alon-Tarsi theorem does not apply to DP-coloring. We define the notion of good covers of prime order which allows us to apply the Combinatorial Nullstellensatz to DP-coloring. We apply these tools to DP-coloring of the cones of certain bipartite graphs and uniquely 3-colorable graphs. We also extend a result of Akbari, Mirrokni, and Sadjad (2006) on unique list colorability to the context of DP-coloring. We establish a sufficient algebraic condition for a graph $G$ to satisfy $χ_{DP}(G) \leq 3$, and we completely determine the DP-chromatic number of squares of all cycles.
