Affordable Access

Packing Triangles in Bounded Degree Graphs

Publication Date
  • Qa075 Electronic Computers. Computer Science


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 (resp. second) problem is polynomially solvable if the maximum degree of the input graph is at most 3 (resp. 4), whereas it is APX-hard for general graphs and NP-hard for planar graphs if the maximum degree is 4 (resp. 5) or more.

There are no comments yet on this publication. Be the first to share your thoughts.