论文标题
简单图表计数边缘色的复杂性
The Complexity of Counting Edge Colorings for Simple Graphs
论文作者
论文摘要
我们证明了在简单图表上计算边缘着色的＃P完整结果。这些增强了[4]的多编码的相应结果。我们证明，对于任何$κ\ ge r \ ge 3 $计数$κ$ - edge y-ed $ r $ grounder-grongular Simple Graphs上的色彩都是＃P-Complete。此外，我们表明，对于平面$ r $的简单图，其中$ r \ in \ {3，4，5 \} $计数带有\ k {appa}颜色的边缘颜色的任何$κ\ ge r $也是＃p-complete。由于任何$ r> 5 $都没有平面$ r $ r $的简单图形，因此这些陈述涵盖了所有有趣的案例，从参数$（κ，r）$方面。
We prove #P-completeness results for counting edge colorings on simple graphs. These strengthen the corresponding results on multigraphs from [4]. We prove that for any $κ\ge r \ge 3$ counting $κ$-edge colorings on $r$-regular simple graphs is #P-complete. Furthermore, we show that for planar $r$-regular simple graphs where $r \in \{3, 4, 5\}$ counting edge colorings with \k{appa} colors for any $κ\ge r$ is also #P-complete. As there are no planar $r$-regular simple graphs for any $r > 5$, these statements cover all interesting cases in terms of the parameters $(κ, r)$.
