Packing triangles in low degree graphs and indifference graphs Original Research Article

We consider the problems of finding the maximum number of vertex-disjoint triangles (image) and edge-disjoint triangles (image) in a simple graph. Both problems are image-hard. The algorithm with the best approximation ratio known so far for these problems has ratio image, 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 image and image that are known to be image-hard: we give an approximation algorithm for image on graphs with maximum degree 4 with ratio slightly less than 1.2, and for image on graphs with maximum degree 5 with ratio 4/3. We also present an exact linear-time algorithm for image on the class of indifference graphs.