TR12-013 Authors: Tomas Feder, Carlos Subi

Publication: 16th February 2012 10:36

Downloads: 2769

Keywords:

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 $G$ can be approximated

within a factor of $\frac{3}{5}$ in polynomial time, and is NP-hard to

approximate within some constant $1-\epsilon$, $0<\epsilon<1$.

We generalize this to the question of finding the largest set of edge-disjoint

copies of a fixed graph $H$ in $G$, which we approximate within

$\frac{2}{|E(H)|+1}$ in polynomial time, and show hard to approximate when

$H=K_r$ or $H=C_r$ is a fixed clique or cycle on at least three vertices.

This relates to a problem solved by Kirkpatrick and Hell.

We finally determine optimal solutions for

the case where $G$ is a clique of any size by examining a

family of dense split graphs. The motivation for the case of cliques is

the theory of block designs, in particular the case of Steiner triple

systems, and

a conjecture of Erd\"{o}s, Faber, and Lovasz which states that the union

of $n$ edge-disjoint cliques of size $n$ has vertex chromatic number $n$.

The connection to this conjecture is obtained through a dualization argument.