Partitioning Sparse Graphs Into Triangles Relations to exact satisfiability and very fast exponential time algorithms
Johan M. M. van Rooij, Hans L. Bodlaender · 2010
We consider the problem of partitioning bounded degree graphs into triangles. We show that this problem is polynomial time solvable on graphs of maximum degree three by giving a linear time algorithm. We also show that this problem becomes