# zbMATH — the first resource for mathematics

A generalization of Lovász’s $$\theta$$ function. (English) Zbl 0726.68060
Polyhedral combinatorics, Proc. Workshop, Morristown/NJ (USA) 1989, DIMACS, Ser. Discret. Math. Theor. Comput. Sci. 1, 19-27 (1990).
Summary: [For the entire collection see Zbl 0722.00003.]
L. Lovász [CBMS-NSF Reg. Conf. Ser. Appl. Math. 50, 91 p. (1986; Zbl 0606.68039)] demonstrated a polynomial-time computable function known as the $$\theta$$ function, which satisfies the following inequality: $$\omega (G)\leq \theta (\bar G)=\vartheta (G)\leq \chi (G),$$ where $$G=(V,E)$$ is a graph, $$\bar G$$ is the complement of G, $$\omega$$ (G) is the size of the largest clique of G, and $$\chi$$ (G) is the chromatic number of G.
We present a polynomial-time computable function $$\vartheta_ k(G)$$ that satisfies the following inequality: $$\omega_ k(G)\leq \vartheta_ k(G)\leq k\vartheta (G),$$ where $$\omega_ k(G)$$ is the cardinality of the largest subset of vertices that can be covered by $$k$$ cliques. This inequality is interesting because $$\omega_ k(G)$$ is known to be an NP- hard parameter, and it provides a better bound for $$\omega_ k(G)$$ than the one provided by $$k\vartheta (G()$$.
##### MSC:
 68R10 Graph theory (including graph drawing) in computer science 68Q25 Analysis of algorithms and problem complexity