## 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) \alphai(G) is the smallest cardinality of an edge set containing at least i edges of each triangle, and (2) \taui(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 \alphai(G) \leq \lfloor(n-1)2/4\rfloor, and every connected graph with n vertices satisfies \alpha1(G) \geq (n-1)/2. There is a positive constant c such that \alpha1(G)+\tau1(G) \geq ce2/3 holds for every graph G with e edges and \alpha1(G)+\tau1(G) \leq e-ce1/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