Abstract
S-functions are mappings from the class of finite graphs into the set of integers, such that certain formal conditions are fulfilled which are shared by the chromatic number, the vertex-connectivity, and the homomorphism-degree. The S-functions form a complete lattice (with respect to their natural partial order). The classes of graphs with values <n under some S-function are studied from a general point of view, and uncountably many S-functions are constructed. Further for every n≥5 a non-trivial base-element of
(see K. WAGNER [7]) is constructed.
Similar content being viewed by others
References
Erdös, P. and Pósa, L.: On independent circuits contained in a graph. Canad.J.Math. 17 (1965), 347–352.
Hadwiger, H.: über eine Klassifikation der Strecken-komplexe. Vierteljahresschr. Naturforsch. Ges. Zürich 88 (1943), 133–142.
Halin, R.: Zur Klassifikation der endlichen Graphen nach H. Hadwiger und K. Wagner. Math. Ann. 172 (1967), 46–78.
Mader, W.: Homomorphieeigenschaften und mittlere Kanten-dichte von Graphen. Math. Ann. 174 (1967), 265–268.
Ore, O.: Theory of graphs. Providence 1962.
Wagner, K.: über eine Eigenschaft der ebenen Komplexe. Math. Ann. 114 (1937), 570–590.
Wagner, K.: Bemerkungen zu Hadwigers Vermutung. Math. Ann. 141 (1960), 433–451.
Wagner, K.: Beweis einer Abschwächung der Hadwiger-Vermutung. Math. Ann. 153 (1964), 139–141.
Wagner, K.: Graphentheorie. Bibliographisches Institut, Mannheim 1970.
Wagner, K. und Halin, R.: Homomorphiebasen von Graphenmengen. Math. Ann. 147 (1962), 126–142.
Author information
Authors and Affiliations
Additional information
Herrn W. BURAU zum 70. Geburtstag gewidmet
Rights and permissions
About this article
Cite this article
Halin, R. S-functions for graphs. J Geom 8, 171–186 (1976). https://doi.org/10.1007/BF01917434
Received:
Issue Date:
DOI: https://doi.org/10.1007/BF01917434