Computational complexity of covering three-vertex multigraphs

DOI10.1016/J.TCS.2015.09.013MaRDI QIDQ897866zbMATH OpenOpenAlexFDO

Authors Jan Kratochvíl, Jan Arne Telle, Marek Tesař

Publication date 8 December 2015

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

Full work available at URL https://doi.org/10.1016/j.tcs.2015.09.013

zbMATH Keywords

computational complexitycovering projectiongraph homomorphism

Mathematics Subject Classification ID

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)

Recommendations

• Computational complexity of covering three-vertex multigraphs
• scientific article; zbMATH DE number 1107736
• Covering regular graphs
• scientific article; zbMATH DE number 91031
• scientific article; zbMATH DE number 1236360

Cites work

• A dichotomy theorem for constraint satisfaction problems on a 3-element set
• Algorithmic aspects of regular graph covers with applications to planar graphs
• An Efficient Algorithm for Graph Isomorphism
• Complexity of hypergraph coloring and Seidel's switching.
• Coverings and minors: Application to local computations in graphs
• 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 1236360 (Why is no real title available?)
• scientific article; zbMATH DE number 1107736 (Why is no real title available?)
• K4,4 ?e has no finite planar cover
• Locally constrained graph homomorphisms -- structure, complexity, and applications
• On possible counterexamples to Negami's planar cover conjecture
• The complexity of satisfiability problems
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• The NP-Completeness of Edge-Coloring

Cited in

(15)

• Covering regular graphs
• List covering of regular multigraphs
• Computational complexity of covering three-vertex multigraphs
• scientific article; zbMATH DE number 6390842 (Why is no real title available?)
• scientific article; zbMATH DE number 91031 (Why is no real title available?)
• scientific article; zbMATH DE number 1107736 (Why is no real title available?)
• An algorithmic framework for locally constrained homomorphisms
• List covering of regular multigraphs with semi-edges
• scientific article; zbMATH DE number 7724194 (Why is no real title available?)
• Computational Complexity of Covering Colored Mixed Multigraphs with Degree Partition Equivalence Classes of Size at Most Two (Extended Abstract)
• An algorithmic framework for locally constrained homomorphisms
• Computational complexity of covering disconnected multigraphs
• Computational complexity of covering coloured mixed multigraphs with simple degree partitions
• Computational complexity of covering multigraphs with semi-edges: small cases
• Computational complexity of covering regular trees

This page was built for publication: Computational complexity of covering three-vertex multigraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q897866)