The complexity of counting edge colorings for simple graphs.

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 κ 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). [ABSTRACT FROM AUTHOR]