Hostname: page-component-74656f9884-2dmjx Total loading time: 0 Render date: 2026-11-11T01:39:15.011Z Has data issue: false hasContentIssue false

The Homomorphism Structure of Classes of Graphs

Published online by Cambridge University Press:  01 January 1999

JAROSLAV NEšETŘIL
Affiliation:
Department of Applied Mathematics, Charles University, Malostranské nám. 25, 118 00 Prague, Czech Republic (e-mail: nesetril@kam.ms.mff.cuni.cz)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

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.

Information

Type
Research Article
Copyright
© 1999 Cambridge University Press