In this paper, we solve a long-standing graph partition problem under vertex-compaction that has been of interest since about 1999. The graph partition problem that we consider in this paper is to decide whether or not it is possible to partition the vertices of a graph into six distinct non-empty sets A, B, C, D, E, and F, such that the vertices in each set are independent, i.e., there is no edge within any set, and an edge is possible but not necessary only between the pairs of sets A and B, B and C, C and D, D and E, E and F, and F and A, and there is no edge between any other pair of sets. We study the problem as the vertex-compaction problem for an irreflexive hexagon (6-cycle). Determining the computational complexity of this problem has been a long-standing problem of interest since about 1999, especially after the results of open problems obtained by the author on a related compaction problem appeared in 1999. We show in this paper that the vertex-compaction problem for an irreflexive hexagon is NP-complete. Our proof can be extended for larger even irreflexive cycles, showing that the vertex-compaction problem for an irreflexive even k-cycle is NP-complete, for all even k \geq 6.

In this paper, we show a very close relationship among the compaction, retraction, and constraint satisfaction problems in the context of reflexive and bipartite graphs. The compaction and retraction problems are special graph coloring problems, and the constraint satisfaction problem is well known to have an important role in artificial intelligence. The relationships we present provide evidence that, similar to the retraction problem, it is likely to be difficult to determine whether for every fixed reflexive or bipartite graph, the compaction problem is polynomial time solvable or NP-complete. In particular, the relationships that we present relate to a long-standing open problem concerning the equivalence of the compaction and retraction problems.

In this paper, we solve a widely publicized open problem posed by Peter Winkler in 1988. The problem is to decide whether or not it is possible to partition the vertices of a graph into four distinct nonempty sets A, B, C, and D, such that there is no edge between the sets A and C, and between the sets B and D, and that there is at least one edge between any other pair of distinct sets. Winkler asked whether this problem is NP-complete. We show in this paper that it is NP-complete. We study the problem as the compaction problem for a reflexive 4-cycle. We also show in this paper that the compaction problem for a reflexive k-cycle is NP-complete for all $k \geq 4$.