Graph Relations and Constrained Homomorphism Partial Orders

Yangjing Long

AutorIn

Yangjing Long

Titel

Graph Relations and Constrained Homomorphism Partial Orders

Zitierfähige Url:

https://nbn-resolving.org/urn:nbn:de:bsz:15-qucosa-154281

Datum der Einreichung

03.04.2014

Datum der Verteidigung

14.10.2014

Abstract (EN)

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.

Freie Schlagwörter (EN)

graph relations, constrained homomorphism orders, R-core, R-cocore

Klassifikation (DDC)

500

GutachterIn