Return to search

Graph Relations and Constrained Homomorphism Partial Orders

We consider constrained variants of graph homomorphisms such as embeddings, monomorphisms, full homomorphisms,
surjective homomorpshims, and locally constrained homomorphisms.
We also introduce a new variation on this theme which derives from
relations between graphs and is related to multihomomorphisms.
This gives a generalization of surjective homomorphisms and naturally leads to notions of R-retractions, R-cores, and R-cocores of graphs. Both \\mbox{R-cores} and R-cocores of graphs are unique up to isomorphism and can be computed in polynomial time.

The theory of the graph homomorphism order is well developed, and from it we consider analogous notions defined for orders induced by constrained homomorphisms.
We identify corresponding cores, prove or disprove universality, characterize gaps and dualities. We give a new and significantly easier proof of the universality of the homomorphism order by showing that even the class of oriented cycles is universal. We provide a systematic approach to simplify the proofs of several earlier results in this area.
We explore in greater detail locally injective homomorphisms on connected graphs, characterize gaps and show universality. We also prove that for every $d\\geq 3$ the homomorphism order on the class of line graphs of graphs with maximum degree $d$ is universal.

Identiferoai:union.ndltd.org:DRESDEN/oai:qucosa:de:qucosa:12966
Date14 October 2014
CreatorsLong, Yangjing
ContributorsStadler, Peter, Jost, J\\\"urgen, Hell, Pavol, der Universit\\\"at Leipzig
Source SetsHochschulschriftenserver (HSSS) der SLUB Dresden
LanguageEnglish
Detected LanguageEnglish
Typedoc-type:doctoralThesis, info:eu-repo/semantics/doctoralThesis, doc-type:Text
Rightsinfo:eu-repo/semantics/openAccess

Page generated in 0.0019 seconds