𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Counting Homomorphisms to Sparse Graphs

✍ Scribed by Jaroslav Nešetřil; Patrice Ossona de Mendez

Book ID
108120718
Publisher
Elsevier Science
Year
2009
Tongue
English
Weight
178 KB
Volume
34
Category
Article
ISSN
1571-0653

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

List Homomorphisms to Reflexive Graphs
List Homomorphisms to Reflexive Graphs
✍ Tomas Feder; Pavol Hell 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 334 KB

Let H be a fixed graph. We introduce the following list homomorphism problem: Given an input graph G and for each vertex v of G a ``list'' L(v) V(H), decide whether or not there is a homomorphism f : We discuss this problem primarily in the context of reflexive graphs, i.e., graphs in which each ve

Inequalities with respect to graph homom
Inequalities with respect to graph homomorphism
✍ Huishan Zhou 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 184 KB

If there is a homomorphism from a graph G onto a graph H, then there exist some inequalities relating 'the degree ratio' of the two graphs which have some interesting corollaries.

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

Complexity of homomorphisms to direct pr
Complexity of homomorphisms to direct products of graphs
✍ Judit Büki; Csaba Szabó 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 55 KB

For a graph G, OAL G asks whether or not an input graph H together with a partial map g : G 2 are trees and NP-complete otherwise.