Extended skew partition problem Original Research Article

A skew partition as defined by Chvátal is a partition of the vertex set of a graph into four nonempty parts image such that there are all possible edges between image and image, and no edges between image and image. We introduce the concept of image-extended skew partition which includes all partitioning problems into image nonempty parts image such that there are all possible edges between the image parts, no edges between the image parts, image, which generalizes the skew partition. We present a polynomial-time algorithm for testing whether a graph admits an image-extended skew partition. As a tool to complete this task we also develop a generalized 2-SAT algorithm, which by itself may have application to other partition problems.