𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Geometric graph homomorphisms

✍ Scribed by Debra L. Boutin; Sally Cockburn

Publisher
John Wiley and Sons
Year
2011
Tongue
English
Weight
159 KB
Volume
69
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

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 defines the geochromatic number as the minimum n so that there is a geometric homomorphism from to a geometric n‐clique. The geochromatic number is related to both the chromatic number and to the minimum number of plane layers of . By providing an infinite family of bipartite geometric graphs, each of which is constructed of two plane layers, which take on all possible values of geochromatic number, we show that these relationships do not determine the geochromatic number. This article also gives necessary (but not sufficient) and sufficient (but not necessary) conditions for a geometric graph to have geochromatic number at most four. As a corollary, we get precise criteria for a bipartite geometric graph to have geochromatic number at most four. This article also gives criteria for a geometric graph to be homomorphic to certain geometric realizations of K~2, 2~ and K~3, 3~. © 2011 Wiley Periodicals, Inc. J Graph Theory 69:97‐113, 2012

📜 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

Homomorphism–homogeneous graphs
Homomorphism–homogeneous graphs
✍ Momchil Rusinov; Pascal Schweitzer 📂 Article 📅 2010 🏛 John Wiley and Sons 🌐 English ⚖ 141 KB

## 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–

Graph homomorphisms through random walks
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

Extremal graphs for homomorphisms
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

On Random Graph Homomorphisms into Z
On Random Graph Homomorphisms into Z
✍ Itai Benjamini; Olle Häggström; Elchanan Mossel 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 319 KB

Given a bipartite connected finite graph G=(V, E) and a vertex v 0 # V, we consider a uniform probability measure on the set of graph homomorphisms f : V Ä Z satisfying f (v 0 )=0. This measure can be viewed as a G-indexed random walk on Z, generalizing both the usual time-indexed random walk and tr