S-functions for graphs (1976)

---

Link: https://link.springer.com/article/10.1007/BF01917434

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 \geq 5$ a non-trivial base-element of $\hat h^\star(n)$ (see K. WAGNER [7]) is constructed.

---