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