Packing triangles in bounded degree graphs
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. (C) 2002 Elsevier Science B.V. All rights reserved.
packing triangles apx-hardness np-hardness planar graphs polynomial algorithm