##
**Zentralblatt MATH**

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

**Zbl.No: ** 857.05077

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

**Title: ** Covering and independence in triangle structures. (In English)

**Source: ** Discrete Math. 150, No.1-3, 89-101 (1996).

**Review: ** A graph is triangular if each edge is contained in at least one triangle. In the paper under review, several results concerning the following two invariants are proved. For i = 1,2 we have: (1) \alpha_{i}(G) is the smallest cardinality of an edge set containing at least i edges of each triangle, and (2) \tau_{i}(G) is the largest cardinality of an edge set containing at most i edges of each triangle. For example, every triangular graph G with n vertices satisfies \alpha_{i}(G) \leq \lfloor(n-1)^{2}/4\rfloor, and every connected graph with n vertices satisfies \alpha_{1}(G) \geq (n-1)/2. There is a positive constant c such that \alpha_{1}(G)+\tau_{1}(G) \geq ce^{2/3} holds for every graph G with e edges and \alpha_{1}(G)+\tau_{1}(G) \leq e-ce^{1/3} for every triangular graph with e edges.

**Reviewer: ** A.Vince (Gainesville)

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

05C35 Extremal problems (graph theory)

05C55 Generalized Ramsey theory

**Keywords: ** covering; independence; triangle; triangular graph

© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag