Locally constrained graph homomorphisms and equitable partitions

DOI10.1016/j.ejc.2007.11.006zbMath1205.05141OpenAlexW2170360372MaRDI QIDQ2427537

Daniël Paulusma, Jan Arne Telle, Jiří Fiala

Publication date: 13 May 2008

Published in: European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL: http://dro.dur.ac.uk/7423/1/7423.pdf

zbMATH Keywords

graph homomorphismsgraph partitiondegree matricesdegree refinement matrixmatrix comparability

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Vertex degrees (05C07) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items (8)

Unique square property, equitable partitions, and product-like graphs ⋮ Comparing Universal Covers in Polynomial Time ⋮ Packing bipartite graphs with covers of complete bipartite graphs ⋮ On the power of synchronization between two adjacent processes ⋮ Block transitivity and degree matrices ⋮ Block transitivity and degree matrices ⋮ Comparing universal covers in polynomial time ⋮ Graph labelings derived from models in distributed computing: A complete complexity classification

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A complete complexity classification of the role assignment problem
• Cantor--Bernstein type theorem for locally constrained graph homomorphisms
• On the complexity of H-coloring
• Finite common coverings of pairs of regular graphs
• Finite common coverings of graphs
• Role colouring a graph
• Covering regular graphs
• Homomorphisms of derivative graphs
• How hard is it to determine if a graph has a 2-role assignment?
• Constructing 5-Arc-Transitive Cubic Graphs
• Partial covers of graphs
• Graph Transformations
• The role assignment model nearly fits most social networks
• Fixed-parameter complexity of \(\lambda\)-labelings

This page was built for publication: Locally constrained graph homomorphisms and equitable partitions