All reports by Author Carlos Subi:

__
TR12-013
| 15th February 2012
__

Tomas Feder, Carlos Subi#### Packing Edge-Disjoint Triangles in Given Graphs

Tomas Feder, Carlos Subi

Given a graph $G$, we consider the problem of finding the largest set

of edge-disjoint triangles contained in $G$. We show that even the

simpler case of decomposing the edges of

a sparse split graph $G$ into edge-disjoint triangles

is NP-complete. We show next that the case of a general ...
more >>>