2020/10/10 by Jin‐Yi Cai, Jin-Yi Cai, Cai, Jin-Yi +2 · 1 citation
Computer Science · Mathematics · #1-planar graph #Advanced Graph Theory Research #Advanced Topology and Set Theory #Artificial intelligence #Chordal graph #Combinatorics #Completeness (order theory) #Computational Complexity (cs.CC) #Computer science #Counting problem #Discrete mathematics #Enhanced Data Rates for GSM Evolution #FOS: Computer and information sciences #Geometry #Graph #Kappa #Limits and Structures in Graph Theory #Mathematics #Planar graph #Simple (philosophy) #Simple graph #cs.CC
paper · pdf · doi:10.48550/arxiv.2010.04910
published in arXiv (Cornell University) (Cornell University)
arxiv created 2020/10/10 · openalex publication_date 2020/10/10 · arxiv updated 2020/10/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/08
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 \kappa 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).