Graphs and homomorphisms

By P. Hell, J. Nesetril. Oxford lecture series in mathematics and its applications, 2026

1,033 citations recorded by the source corpus.

This is a book about graph homomorphisms, intended to introduce this exciting topic to a wide audience. It attempts to bring together what the authors see as the highlights of the theory and its many applications, and could be read as a sampler of this rich theory, and its most interesting results, techniques, and applications, with the hope that the reader will be motivated to further explore the rich literature. It tries not to set its focus too narrowly, bringing together the disparate sources of results, techniques, and points of view; these vary, from algebraic, to algorithmic, applied, extremal, and randomized. This is a second edition of a 2004 OUP book that appeared in the Oxford Lecture Series in Mathematics and Its Applications; the second edition was necessitated by the explosive development that the field underwent in the past two decades. As in the first edition, the topics cover the connections with classical combinatorial notions like graph colourings and products, with algebraic concepts like monoids and categories, and with algorithmic issues related to deciding the existence of a homomorphism. It is updated with the recent breakthroughs in several areas, and discusses, for example, the disproof of Hedetniemi’s product conjecture and the proof of the Feder–Vardi dichotomy conjecture. Moreover, many new topics are introduced, related to sparsity, logic, model theory, and the convergence of structures.

Subfields: Computational Theory and Mathematics

View Paper: https://www.semanticscholar.org/paper/4ee2ddbafefb5e0fc97e2673fb67445318d03ee3

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

Citations in the corpus

Noncommutative Riemannian geometry on graphs (2010, background): “In fact there are different notions in the literature[8] and the most usual of sending vertices to vertices and arrows to arrows is not quite what we want, partly because we have decided to work with simple digraphs in which there are no self-arrows.”
Cohomology of digraphs and (undirected) graphs (2015, methodology): “is easy to check that S is a functor from the category NGR to the full subcategory SGR (see [16]).”
Foundations of Modern Query Languages for Graph Databases (2016, background): “…versions of the isomorphism-based semantics considered in Section 3.1; NP-hardness can be proven for the former by reduction from the graph homomorphism problem (Hell and Nesetril 2004), while for the latter, it can be established by reduction from the subgraph isomorphism problem (Ullmann 1976).”
Counting Graph Homomorphisms (2006, neutral): “Counting Graph Homomorphisms Christian Borgs, Jennifer Chayes, László Lovász, Vera T. Sós, Katalin Vesztergombi February 2006 Contents”
CORES OF SYMMETRIC GRAPHS (2008, background): “Keywords and phrases: graph homomorphism, core graph, rank three graph.”
Schema mappings, data exchange, and metadata management (2005, background): “The concept of homomorphism is a fundamental algebraic concept that been extensively studied in graph theory [21] and in constraint satisfaction [16].”
Chromatic numbers, morphism complexes, and Stiefel-Whitney characteristic classes (2005, background): “essed verbally: edges map to edges. The study of graph homomorphisms is a classical and well-developed subject within combinatorics. The interested reader may want to consult the textbooks [GR01] and [HN04]. Clearly, for any two positive integers mand n, a graph homomorphism ϕ: Km → Kn exists if and”
A Dichotomy Theorem for Nonuniform CSPs (2017, neutral): “A very important special case of the CSP, the (Di)Graph Homomorphism problem and the H -Coloring problem have been actively studied in the graph theory community, see, e.g. [37], [38] and subsequent works by Hell, Feder, Bang-Jensen, Raﬁey and others.”
On a conjecture about edge irregular total labelings (2008, background): “Links between colorings and homomorphisms are presented in more details in the recent monograph [12] by Hell and Nešetřil.”
Covering arrays on graphs: Qualitative independence graphs and extremal set partition theory (2007, background): “This section introduces graph homomorphism; for more information on graph homomorphism see [34, 37, 41].”