Partitioning 2-edge-colored complete multipartite graphs into monochromatic cycles, paths and trees |
| |
Authors: | Zemin Jin Mikio Kano Xueliang Li Bing Wei |
| |
Affiliation: | (1) Center for Combinatorics, LPMC, Nankai University, Tianjin, China;(2) Department of Mathematics, Zhejiang Normal University, Jinhua, China;(3) Department of Computer and Information Science, Ibaraki University, Hitachi, Japan;(4) Department of Mathematics, University of Mississippi, Oxford, USA |
| |
Abstract: | 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. Research supported by NSFC. |
| |
Keywords: | Complete multipartite graphs Graph partitioning Monochromatic subgraphs Complexity |
本文献已被 SpringerLink 等数据库收录! |
|