The Complexity of Counting Edge Colorings for Simple Graphs

10/10/2020

∙

by   Jin-Yi Cai, et al.

∙

0

∙

share

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 κ≥ r ≥ 3 counting κ-edge colorings on r-regular simple graphs is #P-complete. Furthermore, we show that for planar r-regular simple graphs where r ∈{3, 4, 5} counting edge colorings with ąp̨p̨ą colors for any κ≥ 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).