##
**Zentralblatt MATH**

**Publications of (and about) Paul Erdös**

**Zbl.No: ** 766.05063

**Autor: ** Erdös, Paul; Gallai, Tibor; Tuza, Zsolt

**Title: ** Covering the cliques of a graph with vertices. (In English)

**Source: ** Discrete Math. 108, No.1-3, 279-289 (1992).

**Review: ** Here all graphs have order n and isolated vertics are not counted as cliques. The central problem studied is that of estimating the cardinality \tau_{c}(G) of the smallest set that shares a vertex with each clique of G. Among other results it is shown that \tau_{c}(G) \leq n-\sqrt{2n}+ ^{3}/_{2} and a linear time (in the number of edges) algorithm for achieving this bound is proposed. Four associated problems are presented. For example, it is asked if \tau_{c}(G) \leq n-r(n) for all graphs G where r(n) is the largest integer such that every triangle-free graph contains an independent set of r(n) vertices. Also, how large triangle-free induced subgraphs does a K_{4}-free graph G contain.

**Reviewer: ** R.C.Entringer (Albuquerque)

**Classif.: ** * 05C70 Factorization, etc.

05C35 Extremal problems (graph theory)

05C85 Graphic algorithms

**Keywords: ** covering; cliques; linear time algorithm; triangle-free graph

© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag