Packing triangles in low degree graphs and indifference graphs

We consider the problems of finding the maximum number of vertex-disjoint triangles (VTPVTP) and edge-disjoint triangles (ETPETP) in a simple graph. Both problems are NPNP-hard. The algorithm with the best approximation ratio known so far for these problems has ratio 3/2+ɛ3/2+ɛ, a result that follows from a more general algorithm for set packing obtained by Hurkens and Schrijver [On the size of systems of sets every t   of which have an SDR, with an application to the worst-case ratio of heuristics for packing problems, SIAM J. Discrete Math. 2(1) (1989) 68–72]. We present improvements on the approximation ratio for restricted cases of VTPVTP and ETPETP that are known to be APXAPX-hard: we give an approximation algorithm for VTPVTP on graphs with maximum degree 4 with ratio slightly less than 1.2, and for ETPETP on graphs with maximum degree 5 with ratio 4/3. We also present an exact linear-time algorithm for VTPVTP on the class of indifference graphs.