Thesis

### Counting, modular counting and graph homomorphisms

Abstract:

A homomorphism from a graph G to a graph H is a function from V (G) to V (H) that preserves edges. Many combinatorial structures that arise in mathematics and in computer science can be represented naturally as graph homomorphisms and as weighted sums of graph homomorphisms. In this thesis we study the complexity of various problems related to graph homomorphisms.

We first study the problem #kHomsToH of co...

Files:
• (pdf, 1.2MB)

### Authors

More by this author
Department:
Computer Science
Role:
Author

#### Contributors

Department:
Computer Science
Role:
Supervisor
Type of award:
DPhil
Level of award:
Doctoral
Awarding institution:
University of Oxford
Language:
English
Keywords:
Subjects: