Products, retracts, and polymorphisms

View at publisher Summarise with VIRAT
Authors: Pavol Hell, Jaroslav Nešetřil
Cited by: 0
References: 281

Summary

No summary yet. VIRAT can read this paper and write a plain-language summary of its aim, methods, key findings and limitations.

Summarise with VIRAT Free to try with your Science Catalogs account.

Abstract

Abstract Chapter 2 focuses on certain basic constructions that occur frequently in the rest of the book, emphasizing the product and the retract, but also considering other constructs such as the shift graph, the exponential graph, and the Lovász vector—each of which plays an auxiliary role in Chapter 2, and is a useful concept in its own right. The highlights of the discussion of products include a linear algebra based lower bound on the dimension of a graph, a stronger version of the edge reconstruction result from Chapter 1, a discussion of cancellation and unique factorization properties, a construction of graphs with arbitrarily high odd girth and chromatic number, a discussion of counterexamples to Hedetniemi’s product conjecture (related to the exponential graph construction), and an elementary proof of the multiplicativity of oriented cycles of prime power length. For the discussion of retracts, the focus is on structures that are always retracts in reflexive graphs, and characterizations of absolute reflexive retracts in several different ways, including a winning strategy for the cop in the game of cops and robbers. Median graphs are introduced and related to retracts of hypercubes, and an application of median graphs and retractions to a resource location problem is described. The chapter closes with a discussion of polymorphisms and projectivity, which play an important role in subsequent chapters, and in particular for the proof of the graph dichotomy theorem in Chapter 5. For conservative polymorphisms, the emphasis is on forbidden structure characterizations, including those for min ordering and conservative majority, and Maltsev polymorphisms.

Fields of Study & Subjects

Advanced Graph Theory Research Advanced Topology and Set Theory Limits and Structures in Graph Theory

Publication details

Journal / source
Oxford University Press eBooks
Pages
47–113
Publication date
15 February 2026
Language
EN
Document type
Book chapter