𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On recognizing graphs by numbers of homomorphisms

✍ Scribed by Zdeněk Dvořák

Publisher
John Wiley and Sons
Year
2009
Tongue
English
Weight
129 KB
Volume
64
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

Let hom (G, H) be the number of homomorphisms from a graph G to a graph H. A well‐known result of Lovász states that the function hom (·, H) from all graphs uniquely determines the graph H up to isomorphism. We study this function restricted to smaller classes of graphs. We show that several natural classes (2‐degenerate graphs and graphs homomorphic to an arbitrary non‐bipartite graph) are sufficient to recognize all graphs, and provide a description of graph properties that are recognizable by graphs with bounded tree‐width. © 2009 Wiley Periodicals, Inc. J Graph Theory 64: 330–342, 2010

📜 SIMILAR VOLUMES

Jump-number of Means on Graphs
Jump-number of Means on Graphs
✍ Christian Delhommé; Maurice Pouzet; Norbert Sauer 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 153 KB

We prove that the jump-number of a symmetric and idempotent n-ary operation defined on the vertex-set of a graph G is at least min g 4 , g-1 n , where g is the girth of G.

Graphs on the Torus and Geometry of Numb
Graphs on the Torus and Geometry of Numbers
✍ A. Schrijver 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 424 KB

We show that if \(G\) is a graph embedded on the torus \(S\) and each nonnullhomotopic closed curve on \(S\) intersects \(G\) at least \(r\) times, then \(G\) contains at least \(\left\lfloor\frac{3}{4} r\right\rfloor\) pairwise disjoint nonnullhomotopic circuits. The factor \(\frac{3}{4}\) is best

On the chromatic number of disk graphs
On the chromatic number of disk graphs
✍ Malesi?ska, Ewa; Piskorz, Steffen; Wei�enfels, Gerhard 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 172 KB 👁 2 views

Colorings of disk graphs arise in the study of the frequency-assignment problem in broadcast networks. Motivated by the observations that the chromatic number of graphs modeling real networks hardly exceeds their clique number, we examine the related properties of the unit disk (UD) graphs and their

On the interval number of special graphs
On the interval number of special graphs
✍ József Balogh; Pascal Ochem; András Pluhár 📂 Article 📅 2004 🏛 John Wiley and Sons 🌐 English ⚖ 116 KB 👁 1 views

## Abstract The interval number of a graph __G__ is the least natural number __t__ such that __G__ is the intersection graph of sets, each of which is the union of at most __t__ intervals, denoted by __i__(__G__). Griggs and West showed that $i(G)\le \lceil {1\over 2} (d+1)\rceil $. We describe the