*Pavol Hell and Jaroslav Nešetřil*

- Published in print:
- 2004
- Published Online:
- September 2007
- ISBN:
- 9780198528173
- eISBN:
- 9780191713644
- Item type:
- chapter

- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780198528173.003.0001
- Subject:
- Mathematics, Combinatorics / Graph Theory / Discrete Mathematics

This introductory chapter is a sampler of the material covered in the book. It introduces the notation and terminology in the book, and provides motivational examples and applications, many taken up ...
More

This introductory chapter is a sampler of the material covered in the book. It introduces the notation and terminology in the book, and provides motivational examples and applications, many taken up in more detail in later chapters. It gives the flavour of combinatorial aspects, algorithmic aspects, retractions, duality, constraint satisfaction problems, as well as structural properties of homomorphism composition. The highlights of this chapter include a simple proof of the Colouring Interpolation Theorem, a generalization of the No-Homomorphism Lemma, the construction of a triangle-free graph to which all cubic triangle-free graphs are homomorphic, a case of the Edge Reconstruction Conjecture, and a generalization of a theorem of Frucht on graphs with prescribed automorphism groups.Less

This introductory chapter is a sampler of the material covered in the book. It introduces the notation and terminology in the book, and provides motivational examples and applications, many taken up in more detail in later chapters. It gives the flavour of combinatorial aspects, algorithmic aspects, retractions, duality, constraint satisfaction problems, as well as structural properties of homomorphism composition. The highlights of this chapter include a simple proof of the Colouring Interpolation Theorem, a generalization of the No-Homomorphism Lemma, the construction of a triangle-free graph to which all cubic triangle-free graphs are homomorphic, a case of the Edge Reconstruction Conjecture, and a generalization of a theorem of Frucht on graphs with prescribed automorphism groups.

*Pavol Hell and Jaroslav Nešetřil*

- Published in print:
- 2004
- Published Online:
- September 2007
- ISBN:
- 9780198528173
- eISBN:
- 9780191713644
- Item type:
- chapter

- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780198528173.003.0004
- Subject:
- Mathematics, Combinatorics / Graph Theory / Discrete Mathematics

This chapter focuses on the structure, as opposed to just the existence, of the family of homomorphisms among a set of graphs. The difference is noticeable with even just one graph. For instance, a ...
More

This chapter focuses on the structure, as opposed to just the existence, of the family of homomorphisms among a set of graphs. The difference is noticeable with even just one graph. For instance, a graph having only the identity homomorphisms to itself is called rigid; rigid graphs are the building blocks of many constructions. Many useful constructions of rigid graphs are provided, and it is shown that asymptotically almost all graphs are rigid; infinite rigid graphs with arbitrary cardinality are also constructed. The homomorphisms among a set of graphs impose the algebraic structure of a category, and every finite category is represented by a set of graphs. This is the generalization of the theorem of Frucht from Chapter 1. Also, as in the case studied by Frucht, it is shown that the representing graphs can be required to have any of a number of graph theoretic properties. However, these properties cannot include having bounded degrees — somewhat surprisingly, since Frucht proved that cubic graphs represent all finite groups.Less

This chapter focuses on the structure, as opposed to just the existence, of the family of homomorphisms among a set of graphs. The difference is noticeable with even just one graph. For instance, a graph having only the identity homomorphisms to itself is called rigid; rigid graphs are the building blocks of many constructions. Many useful constructions of rigid graphs are provided, and it is shown that asymptotically almost all graphs are rigid; infinite rigid graphs with arbitrary cardinality are also constructed. The homomorphisms among a set of graphs impose the algebraic structure of a category, and every finite category is represented by a set of graphs. This is the generalization of the theorem of Frucht from Chapter 1. Also, as in the case studied by Frucht, it is shown that the representing graphs can be required to have any of a number of graph theoretic properties. However, these properties cannot include having bounded degrees — somewhat surprisingly, since Frucht proved that cubic graphs represent all finite groups.