Packing triangles in bounded degree graphs. (Q1853132)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Packing triangles in bounded degree graphs. |
scientific article |
Statements
Packing triangles in bounded degree graphs. (English)
0 references
21 January 2003
0 references
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.
0 references
Packing triangles
0 references
Polynomial algorithm
0 references
APX-hardness
0 references
Planar graphs
0 references
NP-hardness
0 references
