The fine-grained complexity of approximately counting proper connected colorings (extended abstract)
From MaRDI portal
Publication:6606223
DOI10.1007/978-3-031-49614-1_8MaRDI QIDQ6606223
Robert D. Barish, Tetsuo Shibuya
Publication date: 16 September 2024
edge coloringapproximate countingcounting complexityexponential time hypothesis (ETH)proper connected coloringcounting exponential time hypothesis (\#ETH)\textit{\#P}\textit{NP}
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Characterizations of graphs having large proper connection numbers
- Proper connection of graphs
- Proper connection number of random graphs
- Inapproximability of the Tutte polynomial
- The method of alternating paths
- Random generation of combinatorial structures from a uniform distribution
- Julius Petersen's theory of regular graphs
- Chromatic scheduling and frequency assignment
- A note on alternating cycles in edge-coloured graphs
- Alternating cycles and paths in edge-coloured multigraphs: A survey
- The complexity of counting self-avoiding walks in subgraphs of two-dimensional grids and hypercubes.
- Zur allgemeinen Kurventheorie.
- The theory of regular graphs
- Alternating cycles and trails in \(2\)-edge-coloured complete multigraphs
- Which problems have strongly exponential complexity?
- Alternating paths in edge-colored complete graphs
- Finding paths in graphs avoiding forbidden transitions
- Hardness results for three kinds of colored connections of graphs
- Proper connection with many colors
- Paths and trails in edge-colored graphs
- Minimum degree condition for proper connection number 2
- Graph Theory
- The rainbow connectivity of a graph
- Rainbow connection in graphs
- Exponential Time Complexity of the Permanent and the Tutte Polynomial
- Fine-Grained Reductions from Approximate Counting to Decision
- Paths, Trees, and Flowers
- The Factors of Graphs
- On the (di)graphs with (directed) proper connection number two
- Models and solution techniques for frequency assignment problems
- On the complexity of \(k\)-SAT
This page was built for publication: The fine-grained complexity of approximately counting proper connected colorings (extended abstract)
