✦ LIBER ✦

The complexity of counting graph homomorphisms

✍ Scribed by Martin Dyer; Catherine Greenhill

Publisher: John Wiley and Sons
Year: 2000
Tongue: English
Weight: 229 KB
Volume: 17
Category: Article
ISSN: 1042-9832
DOI: 10.1002/1098-2418(200010/12)17:3/4<260::aid-rsa5>3.0.co;2-w

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

Bi-arc graphs and the complexity of list

Bi-arc graphs and the complexity of list homomorphisms

✍ Tomas Feder; Pavol Hell; Jing Huang 📂 Article 📅 2002 🏛 John Wiley and Sons 🌐 English ⚖ 185 KB

## Abstract Given graphs __G__, __H__, and lists __L__(__v__) ⊆ __V__(__H__), __v__ ε __V__(__G__), a list homomorphism of __G__ to __H__ with respect to the lists __L__ is a mapping __f__ : __V__(__G__) → __V__(__H__) such that __u__v ε __E__(__G__) implies __f__(__u__)__f__(__v__) ε __E__(__H__),

Homomorphisms of graphs into odd cycles

✍ A. M. H. Gerards 📂 Article 📅 1988 🏛 John Wiley and Sons 🌐 English ⚖ 474 KB

Colored Homomorphisms of Colored Mixed G

Colored Homomorphisms of Colored Mixed Graphs

✍ Jaroslav Nešetřil; André Raspaud 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 108 KB

The homomorphisms of oriented or undirected graphs, the oriented chromatic number, the relationship between acyclic coloring number and oriented chromatic number, have been recently studied. Improving and combining earlier techniques of N.

High-girth cubic graphs are homomorphic

High-girth cubic graphs are homomorphic to the Clebsch graph

✍ Matt DeVos; Robert Šámal 📂 Article 📅 2011 🏛 John Wiley and Sons 🌐 English ⚖ 192 KB

We give a (computer assisted) proof that the edges of every graph with maximum degree 3 and girth at least 17 may be 5-colored (possibly improperly) so that the complement of each color class is bipartite. Equivalently, every such graph admits a homomorphism to the Clebsch graph (Fig. 1). Hopkins an

On recognizing graphs by numbers of homo

On recognizing graphs by numbers of homomorphisms

✍ Zdeněk Dvořák 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 129 KB

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

Counting k-component forests of a graph

✍ Wendy Myrvold 📂 Article 📅 1992 🏛 John Wiley and Sons 🌐 English ⚖ 331 KB