J. Fiala
Locally constrained graph homomorphisms and equitable partitions
Fiala, J.; Paulusma, D.; Telle, J.A.
Abstract
We explore the connection between locally constrained graph homomorphisms and degree matrices arising from an equitable partition of a graph. We provide several equivalent characterizations of degree matrices. As a consequence we can efficiently check whether a given matrix M is a degree matrix of some graph and also compute the size of a smallest graph for which it is a degree matrix in polynomial time. We extend the well-known connection between degree refinement matrices of graphs and locally bijective graph homomorphisms to locally injective and locally surjective homomorphisms by showing that these latter types of homomorphisms also impose a quasiorder on degree matrices and a partial order on degree refinement matrices. Computing the degree refinement matrix of a graph is easy, and an algorithm deciding the comparability of two matrices in one of these partial orders could be used as a heuristic for deciding whether a graph G allows a homomorphism of the given type to H. For local surjectivity and injectivity we show that the problem of matrix comparability belongs to the complexity class NP.
Citation
Fiala, J., Paulusma, D., & Telle, J. (2008). Locally constrained graph homomorphisms and equitable partitions. European Journal of Combinatorics, 29(4), 850-880. https://doi.org/10.1016/j.ejc.2007.11.006
Journal Article Type | Article |
---|---|
Publication Date | May 1, 2008 |
Deposit Date | Oct 6, 2010 |
Publicly Available Date | Oct 7, 2010 |
Journal | European Journal of Combinatorics |
Print ISSN | 0195-6698 |
Publisher | Elsevier |
Peer Reviewed | Peer Reviewed |
Volume | 29 |
Issue | 4 |
Pages | 850-880 |
DOI | https://doi.org/10.1016/j.ejc.2007.11.006 |
Public URL | https://durham-repository.worktribe.com/output/1517137 |
Files
Accepted Journal Article
(545 Kb)
PDF
Copyright Statement
NOTICE: this is the author's version of a work that was accepted for publication in European journal of combinatorics.
You might also like
Matching cuts in graphs of high girth and H-free graphs
(2023)
Conference Proceeding
Solving problems on generalized convex graphs via mim-width
(2023)
Journal Article
An algorithmic framework for locally constrained homomorphisms
(2023)
Journal Article
On the price of independence for vertex cover, feedback vertex set and odd cycle transversal
(2023)
Journal Article
Computing Subset Vertex Covers in H-Free Graphs
(2023)
Conference Proceeding
Downloadable Citations
About Durham Research Online (DRO)
Administrator e-mail: dro.admin@durham.ac.uk
This application uses the following open-source libraries:
SheetJS Community Edition
Apache License Version 2.0 (http://www.apache.org/licenses/)
PDF.js
Apache License Version 2.0 (http://www.apache.org/licenses/)
Font Awesome
SIL OFL 1.1 (http://scripts.sil.org/OFL)
MIT License (http://opensource.org/licenses/mit-license.html)
CC BY 3.0 ( http://creativecommons.org/licenses/by/3.0/)
Powered by Worktribe © 2024
Advanced Search