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 $\kappa \ge r \ge 3$ counting $\kappa$-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 $\kappa \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 $(\kappa, r)$.
翻译：我们用简单的图表来计算边际颜色, 证明# P- 完整。 这加强了从 [ 4] 计算多面图的相应结果。 我们证明, 任何$\ kappa\ ge r\ ge 3$ $\ kappa $\ ge 3$ $\ kapa$- ge- sedge 简单图表上的彩色都是 # P- complete 。 此外, 我们显示, 对于平面的$- per$- 常规简单图表来说, $@ 3, 4, 5 $ $ $ 计有\ k{appa} 颜色的边际颜色, 任何$\ ge r$ 的彩色都是 # P- complete 。 由于任何 $ > $ > 5 $ 没有平面的平面 $- 普通的彩色图表, 这些报表包含参数值$ (\ kappa, r) $ 。
相关内容
微信扫码咨询专知VIP会员