𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Independence and graph homomorphisms graph homomorphisms

✍ Scribed by Michael O. Albertson; Lily Chan; Ruth Haas

Publisher
John Wiley and Sons
Year
1993
Tongue
English
Weight
305 KB
Volume
17
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

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 Lemma. For k ≥ 4, a graph with n vertices, odd girth 2__k__+1, and minimum degree exceeding n/(k+1) contains an independent set with at least kn/(2__k__+1) vertices; however, we suspect this is not best possible. © 1993 John Wiley & Sons, Inc.

📜 SIMILAR VOLUMES

Geometric graph homomorphisms
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

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