| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 9514556 | Electronic Notes in Discrete Mathematics | 2005 | 5 Pages |
Abstract
A 2K2-partition of a graph is a partition of its vertex set in four (nonempty) parts a, b, c, d such that each vertex of a is adjacent to every vertex of b, and each vertex of c is adjacent to every vertex of d. We show that determining if a graph G admits a 2K2-partition is NP-complete. This result completely classify the H-Partition Problems. Moreover, the 2K2-Partition Problem is the only NP-complete.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
C.N. Campos, S. Dantas, L. Faria, S. Gravier,