Computational complexity of covering three-vertex multigraphs
type: Item
instance of: scholarly article
title: Computational complexity of covering three-vertex multigraphs
zbMATH Open document ID: 1331.68108
author: Jan Kratochvíl
author: Jan Arne Telle
author: Marek Tesař
published in: Theoretical Computer Science
publication date: 2015-12-08T00:00:00Z
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 68Q17
zbMATH DE Number: 6517431
zbMATH Keywords: computational complexity
zbMATH Keywords: graph homomorphism
zbMATH Keywords: covering projection
MaRDI profile type: Publication
full work available at URL: j.tcs.2015.09.013
OpenAlex ID: W1954345120
cites work: Q4017175
cites work: A dichotomy theorem for constraint satisfaction problems on a 3-element set
cites work: An Efficient Algorithm for Graph Isomorphism
cites work: Coverings and minors: Application to local computations in graphs
cites work: The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
cites work: Algorithmic Aspects of Regular Graph Covers with Applications to Planar Graphs
cites work: Locally constrained graph homomorphisms -- structure, complexity, and applications
cites work: K4,4 ?e has no finite planar cover
cites work: On possible counterexamples to Negami's planar cover conjecture
cites work: The NP-Completeness of Edge-Coloring
cites work: Graph-Theoretic Concepts in Computer Science
cites work: Q4373685
cites work: Q4223772
cites work: Q3831029
cites work: The complexity of satisfiability problems
DOI: 10.1016/J.TCS.2015.09.013
description: scientific article; zbMATH DE number 6517431