Partitioning 2-edge-colored complete multipartite graphs into monochromatic cycles, paths and trees |
| |
| Authors: | Zemin Jin Mikio Kano Xueliang Li Bing Wei |
| |
| Institution: | (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 等数据库收录！ |
|
