Locally constrained graph homomorphisms -- structure, complexity, and applications
From MaRDI portal
(Redirected from Publication:458463)
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)
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
Cites work
- scientific article; zbMATH DE number 1600999 (Why is no real title available?)
- scientific article; zbMATH DE number 3823850 (Why is no real title available?)
- scientific article; zbMATH DE number 4106877 (Why is no real title available?)
- scientific article; zbMATH DE number 3685495 (Why is no real title available?)
- scientific article; zbMATH DE number 3717357 (Why is no real title available?)
- scientific article; zbMATH DE number 91031 (Why is no real title available?)
- scientific article; zbMATH DE number 3460178 (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 2080268 (Why is no real title available?)
- scientific article; zbMATH DE number 2081019 (Why is no real title available?)
- scientific article; zbMATH DE number 3445271 (Why is no real title available?)
- scientific article; zbMATH DE number 2117181 (Why is no real title available?)
- scientific article; zbMATH DE number 3218575 (Why is no real title available?)
- scientific article; zbMATH DE number 2197889 (Why is no real title available?)
- scientific article; zbMATH DE number 3363718 (Why is no real title available?)
- A common cover of graphs and 2-cell embeddings
- A complete complexity classification of the role assignment problem
- A kuratowski theorem for the projective plane
- A linear-time algorithm for testing the truth of certain quantified Boolean formulas
- An Efficient Algorithm for Graph Isomorphism
- Antipodal covering graphs
- Automorphisms of graphs and coverings
- Cantor--Bernstein type theorem for locally constrained graph homomorphisms
- Covering regular graphs
- Coverings and minors: Application to local computations in graphs
- Cyclic labellings with constraints at two distances
- Fibrations of graphs
- Finite common coverings of graphs
- Finite common coverings of pairs of regular graphs
- Fixed-parameter complexity of \(\lambda\)-labelings
- Generating all graph coverings by permutation voltage assignments
- Graph Labelings Derived from Models in Distributed Computing
- Graph minors. XX: Wagner's conjecture
- Graph-theoretic concepts in computer science. 32nd international workshop, WG 2006, Bergen, Norway, June 22--24, 2006. Revised papers
- Graphs on surfaces
- Homomorphisms of derivative graphs
- K4,4 ?e has no finite planar cover
- Labelling Graphs with a Condition at Distance 2
- Locally Injective Graph Homomorphism: Lists Guarantee Dichotomy
- Network Analysis
- On possible counterexamples to Negami's planar cover conjecture
- On the computational complexity of partial covers of theta graphs
- Partial covers of graphs
- Role colouring a graph
- The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
- Topology of finite graphs
- Two graphs without planar covers
Cited in
(39)- Mathematical Foundations of Computer Science 2005
- Lower bounds for the graph homomorphism problem
- Packing bipartite graphs with covers of complete bipartite graphs
- Fast exact algorithm for \(L(2,1)\)-labeling of graphs
- Fast dynamic programming for locally checkable vertex subset and vertex partitioning problems
- Complexity of correspondence \(H\)-colourings
- Creating a network-state homomorphism through optimization
- Unfoldings and Coverings of Weighted Graphs
- Computing vertex-surjective homomorphisms to partially reflexive trees
- Computational Complexity of Covering Colored Mixed Multigraphs with Degree Partition Equivalence Classes of Size at Most Two (Extended Abstract)
- Comparing Universal Covers in Polynomial Time
- Star colouring of regular graphs meets weaving and line graphs
- Mike Fellows: Weaving the Web of Mathematics and Adventure
- Star colouring of bounded degree graphs and regular graphs
- Growth rates of permutation grid classes, tours on graphs, and the spectral radius
- Parameterized counting of partially injective homomorphisms
- Computing vertex-surjective homomorphisms to partially reflexive trees
- The Complexity of Boolean Surjective General-Valued CSPs
- Colouring, constraint satisfaction, and complexity
- Computational complexity of covering three-vertex multigraphs
- An algorithmic framework for locally constrained homomorphisms
- The Glasgow subgraph solver: using constraint programming to tackle hard subgraph isomorphism problem variants
- Locally constrained graph homomorphisms and equitable partitions
- Fast exact algorithm for \(L(2,1)\)-labeling of graphs
- Finding vertex-surjective graph homomorphisms
- Partial covers of graphs
- On incidence coloring conjecture in Cartesian products of graphs
- Cantor--Bernstein type theorem for locally constrained graph homomorphisms
- Graph covers: where topology meets computer science, and simple means difficult
- Universality of intervals of line graph order
- Locally constrained homomorphisms on graphs of bounded treewidth and bounded degree
- An algorithmic framework for locally constrained homomorphisms
- Counting restricted homomorphisms via Möbius inversion over matroid lattices
- 3-connected reduction for regular graph covers
- Surjective \(H\)-colouring: new hardness results
- Exact algorithm for graph homomorphism and locally injective graph homomorphism
- List covering of regular multigraphs with semi-edges
- Locally constrained homomorphisms on graphs of bounded treewidth and bounded degree
- List covering of regular multigraphs
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)
