Welcome!
To use the personalized features of this site, please log in or register.
If you have forgotten your username or password, we can help.
|
 |
Partitioning 2-edge-colored complete multipartite graphs into monochromatic cycles, paths and trees
| |
|
Partitioning 2-edge-colored complete multipartite graphs into monochromatic cycles, paths and trees
Zemin Jin1, 2  , Mikio Kano3 , Xueliang Li1 and Bing Wei4
| (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 |
Published online: 17 May 2006
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.
Keywords Complete multipartite graphs - Graph partitioning - Monochromatic subgraphs - Complexity
Research supported by NSFC.
Fulltext Preview (Small, Large)
 References secured to subscribers.
|
|
|
|
|
|