Article contents
The Homomorphism Structure of Classes of Graphs
Published online by Cambridge University Press: 01 January 1999
Abstract
We consider three aspects of homomorphisms of graphs and hypergraphs which are related to the structure of colour classes: (1) density, (2) the fractal property and (3) the generation of colour classes. In particular, we prove a density theorem for hypergraphs and show that, for connected oriented graphs, all jumps are balanced (and give an example to show that connectivity is needed here). We also show that a Hajós-type theorem holds for any colour class of undirected graphs, thus providing further evidence of the well-known ‘non-effective’ character of Hajós' theorem.
- Type
- Research Article
- Information
- Copyright
- © 1999 Cambridge University Press
- 9
- Cited by