✦ LIBER ✦

Packing triangles in bounded degree graphs

✍ Scribed by Alberto Caprara; Romeo Rizzi

Publisher: Elsevier Science
Year: 2002
Tongue: English
Weight: 103 KB
Volume: 84
Category: Article
ISSN: 0020-0190
DOI: 10.1016/s0020-0190(02)00274-0

No coin nor oath required. For personal study only.

✦ Synopsis

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 is APX-hard for general graphs and NP-hard for planar graphs if the maximum degree is 4 (respectively 5) or more.

📜 SIMILAR VOLUMES

Packing and covering triangles in graphs

✍ P.E. Haxell 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 184 KB

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

Degree sequences in triangle-free graphs

✍ Paul Erdős; Siemion Fajtlowicz; William Staton 📂 Article 📅 1991 🏛 Elsevier Science 🌐 English ⚖ 250 KB

Judicious partitions of bounded-degree g

Judicious partitions of bounded-degree graphs

✍ B. Bollobás; A. D. Scott 📂 Article 📅 2004 🏛 John Wiley and Sons 🌐 English ⚖ 118 KB 👁 1 views

## Abstract We prove results on partitioning graphs __G__ with bounded maximum degree. In particular, we provide optimal bounds for bipartitions __V__(__G__) = __V__~1~ ∪ __V__~2~ in which we minimize {__e__(__V__~1~), __e__(__V__~2~)}. © 2004 Wiley Periodicals, Inc. J Graph Theory 46: 131–143, 200

Degree sum for a triangle in a graph

✍ Genghua Fan 📂 Article 📅 1988 🏛 John Wiley and Sons 🌐 English ⚖ 379 KB 👁 1 views

Let %(n; e) denote the class of graphs on n vertices and e edges. Define f(n, e) = min max{C:=, d(u,):{u,, up, uJ} induces a triangle in G}, where the maximum is taken over all triangles in the graph G and the minimum is taken over all G in %(n; e). From Turan's theorem, f(n, e) = 0 if e 5 n 2 / 4 ;

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__

Decreasing the diameter of bounded degre

Decreasing the diameter of bounded degree graphs

✍ Noga Alon; András Gyárfás; Miklós Ruszinkó 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 118 KB 👁 2 views