Partitioning 2-edge-colored complete multipartite graphs into monochromatic cycles, paths and trees. (English) Zbl 1137.05057
Summary: In this paper we consider the problem of partitioning complete multipartite graphs with edges colored by 2 colors into the minimum number of vertex disjoint monochromatic cycles, paths and trees, respectively. For general graphs we simply address the decision version of these three problems the 2-PGMC, 2-PGMP and 2-PGMT problems, respectively. We show that both 2-PGMC and 2-PGMP problems are NP-complete for complete multipartite graphs and the 2-PGMT problem is NP-complete for bipartite graphs. This also implies that all these three problems are NP-complete for general graphs, which solves a question proposed by the authors in a previous paper. Nevertheless, we show that the 2-PGMT problem can be solved in polynomial time for complete multipartite graphs.
MSC:
| 05C70 | Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) |
| 05C85 | Graph algorithms (graph-theoretic aspects) |
| 90C35 | Programming involving graphs or networks |
| 05C15 | Coloring of graphs and hypergraphs |
| 05C38 | Paths and cycles |
| 05C05 | Trees |
References:
| [1] | Brandstadt A (1996) Partitions of graphs into one or two independent sets and cliques. Discrete Math 152:47–54 · Zbl 0853.68140 · doi:10.1016/0012-365X(94)00296-U |
| [2] | Enomoto H (2001) Graph partition problems into cycles and paths. Discrete Math 233:93–101 · Zbl 0985.05036 · doi:10.1016/S0012-365X(00)00229-6 |
| [3] | Erdös P, Gyárfás A, Pyber L (1991) Vertex coverings by monochromatic cycles and trees. J Combin Theory, Ser B 51:90–95 · Zbl 0766.05062 · doi:10.1016/0095-8956(91)90007-7 |
| [4] | Feder T, Hell P, Klein S, Motwani R (1999) Complexity of graph partition problems. Proceedings of Thirty-First Annual ACM Symposium on Theory of Computing, pp. 464–472 · Zbl 1345.68171 |
| [5] | Feder T, Motwani R (1995) Clique partitions, graph compression and Speeding-Up algorithms. J Computer and System Sciences 51:261–272 · Zbl 0831.68073 · doi:10.1006/jcss.1995.1065 |
| [6] | Garey MR, Johnson DS (1979). Computers and intractability, W.H. Freeman, San Francisco |
| [7] | Golumbic MC (1980) Algorithmic graph theory and perfect graphs. Academic Press, New York · Zbl 0541.05054 |
| [8] | Gyárfás A (1983) Vertex coverings by monochromatic paths and cycles. J Graph Theory 7:131–135 · Zbl 0511.05046 · doi:10.1002/jgt.3190070116 |
| [9] | Haxell PE (1997) Partitioning complete bipartite graphs by monochromatic cycles. J Combin Theory Ser B 69:210–218 · Zbl 0867.05022 · doi:10.1006/jctb.1997.1737 |
| [10] | Haxell PE, Kohayakawa Y (1996) Partitioning by monochromatic trees. J Combin Theory Ser B 68:218–222 · Zbl 0861.05018 · doi:10.1006/jctb.1996.0065 |
| [11] | Holyer L (1981) The NP-completeness of some edge-partition problems. SIAM J Comput 10:713–717 · Zbl 0468.68069 · doi:10.1137/0210054 |
| [12] | Jin Z, Li X (2004a) The complexity for partitioning graphs by monochromatic trees, cycles and paths. International J Computer Math 81(11):1357–1362 · Zbl 1078.05021 · doi:10.1080/00207160412331290685 |
| [13] | Jin Z, Li X (2004b) Vertex partitions of r-edge-colored graphs. Submitted · Zbl 1150.05008 |
| [14] | Kaneko A, Kano M, Suzuki K (2005) Partitioning complete multipartite graphs by monochromatic trees. J Graph Theory 48(2):133–141 · Zbl 1063.05043 · doi:10.1002/jgt.20044 |
| [15] | MacGillivray G, Yu ML (1999) Generalized partitions of graphs. Disc Appl Math 91:143–153 · Zbl 0917.05056 · doi:10.1016/S0166-218X(98)00124-3 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
