Locally constrained graph homomorphisms -- structure, complexity, and applications
From MaRDI portal
Publication:458463
DOI10.1016/J.COSREV.2008.06.001zbMATH Open1302.05122OpenAlexW1975912662MaRDI QIDQ458463FDOQ458463
Authors: Jiří Fiala, Jan Kratochvíl 
Publication date: 7 October 2014
Published in: Computer Science Review (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.cosrev.2008.06.001
Recommendations
- Locally constrained homomorphisms on graphs of bounded treewidth and bounded degree
- Locally constrained homomorphisms on graphs of bounded treewidth and bounded degree
- Exact algorithm for graph homomorphism and locally injective graph homomorphism
- scientific article; zbMATH DE number 861321
- Cantor--Bernstein type theorem for locally constrained graph homomorphisms
Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Research exposition (monographs, survey articles) pertaining to combinatorics (05-02) Coloring of graphs and hypergraphs (05C15) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Graph minors. XX: Wagner's conjecture
- A linear-time algorithm for testing the truth of certain quantified Boolean formulas
- Graphs on surfaces
- The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
- A kuratowski theorem for the projective plane
- Labelling Graphs with a Condition at Distance 2
- Title not available (Why is that?)
- Topology of finite graphs
- Automorphisms of graphs and coverings
- Title not available (Why is that?)
- Role colouring a graph
- Coverings and minors: Application to local computations in graphs
- Title not available (Why is that?)
- Title not available (Why is that?)
- A complete complexity classification of the role assignment problem
- Generating all graph coverings by permutation voltage assignments
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Homomorphisms of derivative graphs
- Fibrations of graphs
- Fixed-parameter complexity of \(\lambda\)-labelings
- An Efficient Algorithm for Graph Isomorphism
- Title not available (Why is that?)
- Finite common coverings of graphs
- Covering regular graphs
- Title not available (Why is that?)
- Title not available (Why is that?)
- K4,4 ?e has no finite planar cover
- Partial covers of graphs
- Title not available (Why is that?)
- Graph Labelings Derived from Models in Distributed Computing
- A common cover of graphs and 2-cell embeddings
- Finite common coverings of pairs of regular graphs
- Cyclic labellings with constraints at two distances
- On the computational complexity of partial covers of theta graphs
- Antipodal covering graphs
- Locally Injective Graph Homomorphism: Lists Guarantee Dichotomy
- Title not available (Why is that?)
- On possible counterexamples to Negami's planar cover conjecture
- Two graphs without planar covers
- Title not available (Why is that?)
- Title not available (Why is that?)
- Network Analysis
- Cantor--Bernstein type theorem for locally constrained graph homomorphisms
- Graph-theoretic concepts in computer science. 32nd international workshop, WG 2006, Bergen, Norway, June 22--24, 2006. Revised papers
Cited In (38)
- Fast exact algorithm for \(L(2,1)\)-labeling of graphs
- Fast dynamic programming for locally checkable vertex subset and vertex partitioning problems
- Star colouring of bounded degree graphs and regular graphs
- Comparing Universal Covers in Polynomial Time
- Graph covers: where topology meets computer science, and simple means difficult
- Mike Fellows: Weaving the Web of Mathematics and Adventure
- Colouring, constraint satisfaction, and complexity
- An algorithmic framework for locally constrained homomorphisms
- Surjective \(H\)-colouring: new hardness results
- Finding vertex-surjective graph homomorphisms
- Fast exact algorithm for \(L(2,1)\)-labeling of graphs
- Parameterized counting of partially injective homomorphisms
- Computing vertex-surjective homomorphisms to partially reflexive trees
- On incidence coloring conjecture in Cartesian products of graphs
- Locally constrained homomorphisms on graphs of bounded treewidth and bounded degree
- Packing bipartite graphs with covers of complete bipartite graphs
- Locally constrained graph homomorphisms and equitable partitions
- Lower bounds for the graph homomorphism problem
- Mathematical Foundations of Computer Science 2005
- Computational complexity of covering three-vertex multigraphs
- Cantor--Bernstein type theorem for locally constrained graph homomorphisms
- 3-connected reduction for regular graph covers
- The Complexity of Boolean Surjective General-Valued CSPs
- Universality of intervals of line graph order
- List covering of regular multigraphs
- An algorithmic framework for locally constrained homomorphisms
- Unfoldings and Coverings of Weighted Graphs
- Growth rates of permutation grid classes, tours on graphs, and the spectral radius
- Computing vertex-surjective homomorphisms to partially reflexive trees
- The Glasgow subgraph solver: using constraint programming to tackle hard subgraph isomorphism problem variants
- Locally constrained homomorphisms on graphs of bounded treewidth and bounded degree
- Computational Complexity of Covering Colored Mixed Multigraphs with Degree Partition Equivalence Classes of Size at Most Two (Extended Abstract)
- Complexity of correspondence \(H\)-colourings
- Partial covers of graphs
- List covering of regular multigraphs with semi-edges
- Exact algorithm for graph homomorphism and locally injective graph homomorphism
- Star colouring of regular graphs meets weaving and line graphs
- Counting restricted homomorphisms via Möbius inversion over matroid lattices
Uses Software
This page was built for publication: Locally constrained graph homomorphisms -- structure, complexity, and applications
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q458463)
