✦ LIBER ✦

Homomorphism–homogeneous graphs

✍ Scribed by Momchil Rusinov; Pascal Schweitzer

Publisher: John Wiley and Sons
Year: 2010
Tongue: English
Weight: 141 KB
Volume: 65
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.20478

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

We answer two open questions posed by Cameron and Nesetril concerning homomorphism–homogeneous graphs. In particular we show, by giving a characterization of these graphs, that extendability to monomorphism or to homomorphism leads to the same class of graphs when defining homomorphism–homogeneity. Further, we show that there are homomorphism–homogeneous graphs that do not contain the Rado graph as a spanning subgraph answering the second open question. We also treat the case of homomorphism–homogeneous graphs with loops allowed, showing that the corresponding decision problem is co–NP complete. Finally, we extend the list of considered morphism–types and show that the graphs for which monomorphisms can be extended to epimor‐phisms are complements of homomorphism–homogeneous graphs. © 2010 Wiley Periodicals, Inc. J Graph Theory 65: 253–261, 2010

📜 SIMILAR VOLUMES

Independence and graph homomorphisms gra

Independence and graph homomorphisms graph homomorphisms

✍ Michael O. Albertson; Lily Chan; Ruth Haas 📂 Article 📅 1993 🏛 John Wiley and Sons 🌐 English ⚖ 305 KB

## Abstract A graph with __n__ vertices that contains no triangle and no 5‐cycle and minimum degree exceeding __n__/4 contains an independent set with at least (3__n__)/7 vertices. This is best possible. The proof proceeds by producing a homomorphism to the 7‐cycle and invoking the No Homomorphism

Geometric graph homomorphisms

✍ Debra L. Boutin; Sally Cockburn 📂 Article 📅 2011 🏛 John Wiley and Sons 🌐 English ⚖ 159 KB

## Abstract A __geometric graph__ is a simple graph drawn on points in the plane, in general position, with straightline edges. A __geometric__ __homomorphism__ from to is a vertex map that preserves adjacencies and crossings. This work proves some basic properties of geometric homomorphisms and

Extremal graphs for homomorphisms

✍ Jonathan Cutler; A. J. Radcliffe 📂 Article 📅 2011 🏛 John Wiley and Sons 🌐 English ⚖ 219 KB

The study of graph homomorphisms has a long and distinguished history, with applications in many areas of graph theory. There has been recent interest in counting homomorphisms, and in particular on the question of finding upper bounds for the number of homomorphisms from a graph G into a fixed imag

Finite homomorphism-homogeneous tourname

Finite homomorphism-homogeneous tournaments with loops

✍ Andreja Ilić; Dragan Mašulović; Uroš Rajković 📂 Article 📅 2008 🏛 John Wiley and Sons 🌐 English ⚖ 152 KB

## Abstract A structure is called homogeneous if every isomorphism between finite substructures of the structure extends to an automorphism of the structure. Recently, Cameron and Nešetřil introduced a relaxed version of homogeneity: we say that a structure is homomorphism‐homogeneous if every homo

Homomorphism bounds for oriented planar

Homomorphism bounds for oriented planar graphs

✍ T. H. Marshall 📂 Article 📅 2007 🏛 John Wiley and Sons 🌐 English ⚖ 202 KB

## Abstract If ${\cal C}$ is a class of oriented graphs (directed graphs without opposite arcs), then an oriented graph is a __homomorphism bound__ for ${\cal C}$ if there is a homomorphism from each graph in ${\cal C}$ to __H__. We find some necessary conditions for a graph to be a homomorphism bo

Graph homomorphisms through random walks

✍ Amir Daneshgar; Hossein Hajiabolhassan 📂 Article 📅 2003 🏛 John Wiley and Sons 🌐 English ⚖ 174 KB

## Abstract In this paper we introduce some general necessary conditions for the existence of graph homomorphisms, which hold in both directed and undirected cases. Our method is a combination of Diaconis and Saloff–Coste comparison technique for Markov chains and a generalization of Haemers interl