Some results on triangle partitions

الأصل · EN

We show that there exist efficient algorithms for the triangle packing problem in colored permutation graphs, complete multipartite graphs, distance-hereditary graphs, k-modular permutation graphs and complements of k-partite graphs (when k is fixed). We show that there is an efficient algorithm for C₄-packing on bipartite permutation graphs and we show that C₄-packing on bipartite graphs is NP-complete. We characterize the cobipartite graphs that have a triangle partition.