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()\).
68R10 Graph theory (including graph drawing) in computer science
68Q25 Analysis of algorithms and problem complexity