Locally constrained graph homomorphisms -- structure, complexity, and applications

DOI10.1016/j.cosrev.2008.06.001zbMath1302.05122OpenAlexW1975912662MaRDI QIDQ458463

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

Mathematics Subject Classification ID

Research exposition (monographs, survey articles) pertaining to combinatorics (05-02) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items

Star colouring of bounded degree graphs and regular graphs ⋮ Lower Bounds for the Graph Homomorphism Problem ⋮ On incidence coloring conjecture in Cartesian products of graphs ⋮ Mike Fellows: Weaving the Web of Mathematics and Adventure ⋮ 3-connected reduction for regular graph covers ⋮ List covering of regular multigraphs ⋮ Fast dynamic programming for locally checkable vertex subset and vertex partitioning problems ⋮ Fast exact algorithm for \(L(2,1)\)-labeling of graphs ⋮ Complexity of correspondence \(H\)-colourings ⋮ An algorithmic framework for locally constrained homomorphisms ⋮ The Glasgow Subgraph Solver: Using Constraint Programming to Tackle Hard Subgraph Isomorphism Problem Variants ⋮ Graph covers: where topology meets computer science, and simple means difficult ⋮ Unfoldings and Coverings of Weighted Graphs ⋮ List covering of regular multigraphs with semi-edges ⋮ Computational complexity of covering three-vertex multigraphs ⋮ The Complexity of Boolean Surjective General-Valued CSPs ⋮ Packing bipartite graphs with covers of complete bipartite graphs ⋮ Colouring, constraint satisfaction, and complexity ⋮ Exact algorithm for graph homomorphism and locally injective graph homomorphism ⋮ Computing Vertex-Surjective Homomorphisms to Partially Reflexive Trees ⋮ Fast Exact Algorithm for L(2,1)-Labeling of Graphs ⋮ Surjective \(H\)-colouring: new hardness results ⋮ Computing vertex-surjective homomorphisms to partially reflexive trees ⋮ Finding vertex-surjective graph homomorphisms ⋮ Parameterized counting of partially injective homomorphisms ⋮ Universality of intervals of line graph order ⋮ Counting Restricted Homomorphisms via Möbius Inversion over Matroid Lattices ⋮ Growth rates of permutation grid classes, tours on graphs, and the spectral radius ⋮ Locally constrained homomorphisms on graphs of bounded treewidth and bounded degree

Uses Software

• nauty

Cites Work

• Graph minors. XX: Wagner's conjecture
• A complete complexity classification of the role assignment problem
• 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
• Topology of finite graphs
• A common cover of graphs and 2-cell embeddings
• Finite common coverings of pairs of regular graphs
• Finite common coverings of graphs
• Role colouring a graph
• Generating all graph coverings by permutation voltage assignments
• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• Coverings and minors: Application to local computations in graphs
• Covering regular graphs
• Automorphisms of graphs and coverings
• Cyclic labellings with constraints at two distances
• On the computational complexity of partial covers of theta graphs
• Homomorphisms of derivative graphs
• Antipodal covering graphs
• Locally Injective Graph Homomorphism: Lists Guarantee Dichotomy
• Graph Labelings Derived from Models in Distributed Computing
• A kuratowski theorem for the projective plane
• Labelling Graphs with a Condition at Distance 2
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• K4,4 ?e has no finite planar cover
• On possible counterexamples to Negami's planar cover conjecture
• Partial covers of graphs
• Two graphs without planar covers
• An Efficient Algorithm for Graph Isomorphism
• Network Analysis
• Fixed-parameter complexity of \(\lambda\)-labelings
• Fibrations of graphs
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item