Computational complexity of covering multigraphs with semi-edges: small cases
From MaRDI portal
Planar graphs; geometric and topological aspects of graph theory (05C10) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)
Cites work
- 3-connected reduction for regular graph covers
- A complete complexity classification of the role assignment problem
- Algorithmic aspects of regular graph covers with applications to planar graphs
- An Efficient Algorithm for Graph Isomorphism
- Antipodal covering graphs
- Automorphisms of graphs and coverings
- Complexity of hypergraph coloring and Seidel's switching.
- Computational complexity of covering disconnected multigraphs
- Computational complexity of covering disconnected multigraphs
- Computational complexity of covering three-vertex multigraphs
- Computational Complexity of Covering Colored Mixed Multigraphs with Degree Partition Equivalence Classes of Size at Most Two (Extended Abstract)
- Covering regular graphs
- Coverings and minors: Application to local computations in graphs
- Defective and clustered graph colouring
- Double covers of cubic graphs with oddness 4
- Elementary abelian covers of graphs
- Finite common coverings of graphs
- Finite common coverings of pairs of regular graphs
- Generating all graph coverings by permutation voltage assignments
- Graph labelings derived from models in distributed computing: A complete complexity classification
- Harmonic morphisms of graphs. Part I: Graph coverings
- scientific article; zbMATH DE number 4106877 (Why is no real title available?)
- scientific article; zbMATH DE number 91031 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 1236360 (Why is no real title available?)
- scientific article; zbMATH DE number 512941 (Why is no real title available?)
- scientific article; zbMATH DE number 1107736 (Why is no real title available?)
- scientific article; zbMATH DE number 1953187 (Why is no real title available?)
- scientific article; zbMATH DE number 2080268 (Why is no real title available?)
- scientific article; zbMATH DE number 3445271 (Why is no real title available?)
- scientific article; zbMATH DE number 3450230 (Why is no real title available?)
- scientific article; zbMATH DE number 2111730 (Why is no real title available?)
- scientific article; zbMATH DE number 7724194 (Why is no real title available?)
- K4,4 ?e has no finite planar cover
- Lifting graph automorphisms by voltage assignments
- List covering of regular multigraphs
- Local computations in graphs: the case of cellular edge local computations
- Locally constrained graph homomorphisms -- structure, complexity, and applications
- Locally constrained homomorphisms on graphs of bounded treewidth and bounded degree
- Locally Injective Graph Homomorphism: Lists Guarantee Dichotomy
- Matching theory
- Modular operads
- Nowhere-zero 5-flows on cubic graphs with oddness 4
- NP completeness of finding the chromatic index of regular graphs
- On cycle-double covers of graphs of small oddness
- On possible counterexamples to Negami's planar cover conjecture
- On the complexity of planar covering of small graphs
- Packing bipartite graphs with covers of complete bipartite graphs
- Paths, Trees, and Flowers
- Regular embeddings of canonical double coverings of graphs
- Revisiting Leighton’s theorem with the Haar measure
- Sparsely intersecting perfect matchings in cubic graphs
- The complexity of locally injective homomorphisms
- The complexity of satisfiability problems
- The theory of regular graphs
- Two generalisations of Leighton's theorem (with an appendix by Giles Gardam and Daniel J. Woodhouse)
- Two graphs without planar covers
This page was built for publication: Computational complexity of covering multigraphs with semi-edges: small cases
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6885370)
