## 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 \tauc(G) of the smallest set that shares a vertex with each clique of G. Among other results it is shown that \tauc(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 \tauc(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 K4-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