✦ LIBER ✦

Packing and covering triangles in graphs

✍ Scribed by P.E. Haxell

Publisher: Elsevier Science
Year: 1999
Tongue: English
Weight: 184 KB
Volume: 195
Category: Article
ISSN: 0012-365X
DOI: 10.1016/s0012-365x(98)00183-6

No coin nor oath required. For personal study only.

✦ Synopsis

It is shown that if G is a graph such that the maximum size of a set of pairwise edge-disjoint triangles is v(G), then there is a set C of edges of G of size at most (3 -e)v(G) such that E(T) N C 7~ 0 for every triangle T of G, where e> 3. This is the first nontrivial bound known for a long-standing conjecture of Tuza.

📜 SIMILAR VOLUMES

Packing triangles in bounded degree grap

Packing triangles in bounded degree graphs

✍ Alberto Caprara; Romeo Rizzi 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 103 KB

We consider the two problems of finding the maximum number of node disjoint triangles and edge disjoint triangles in an undirected graph. We show that the first (respectively second) problem is polynomially solvable if the maximum degree of the input graph is at most 3 (respectively 4), whereas it i

Packing and covering dense graphs

✍ Noga Alon; Yair Caro; Raphael Yuster 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 498 KB 👁 1 views

Covering and packing in graphs IV: Linea

Covering and packing in graphs IV: Linear arboricity

✍ Jin Akiyama; Geoffrey Exoo; Frank Harary 📂 Article 📅 1981 🏛 John Wiley and Sons 🌐 English ⚖ 192 KB

Packing triangles in a graph and its com

Packing triangles in a graph and its complement

✍ Peter Keevash; Benny Sudakov 📂 Article 📅 2004 🏛 John Wiley and Sons 🌐 English ⚖ 127 KB 👁 1 views

## Abstract How few edge‐disjoint triangles can there be in a graph __G__ on __n__ vertices and in its complement $\overline {G}$? This question was posed by P. Erdős, who noticed that if __G__ is a disjoint union of two complete graphs of order __n__/2 then this number is __n__^2^/12 + __o__(__n__

On a conjecture of Tuza about packing an

On a conjecture of Tuza about packing and covering of triangles

✍ Michael Krivelevich 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 312 KB

Zs. Tuza conjectured that if a simple graph G does not contain more than k pairwise edge disjoint triangles, then there exists a set of at most 2k edges which meets all triangles in G. We prove this conjecture for K,, 3 -free graphs (graphs that do not contain a homeomorph of K,. 3). Two fractional

Covering and packing in graphs—V: Mispac

Covering and packing in graphs—V: Mispacking subcubes in hypercubes

✍ Niall Graham; Frank Harary 📂 Article 📅 1988 🏛 Elsevier Science 🌐 English ⚖ 236 KB