The complexity of counting edge colorings for simple graphs

DOI10.1016/j.tcs.2021.07.033OpenAlexW3189088987MaRDI QIDQ2232603

Artem Govorov, Jin-Yi Cai

Publication date: 6 October 2021

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2010.04910

zbMATH Keywords

edge coloringplatonic solidsfour color theorem\#P-completenessholant problemscomplexity of counting problems

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The complexity of counting edge colorings and a dichotomy for some higher domain Holant problems
• Graph Theory
• On the unique satisfiability problem
• The NP-Completeness of Edge-Coloring
• Infinite Families of Nontrivial Trivalent Graphs Which are Not Tait Colorable
• On Isomorphisms and Density of $NP$ and Other Complete Sets
• Hamiltonian Cycles and Uniquely Edge Colourable Graphs
• Complexity Dichotomies for Counting Problems
• NP completeness of finding the chromatic index of regular graphs