In graph theory, a skew partition of a graph is a partition of its vertices into two subsets, such that the induced subgraph formed by one of the two subsets is disconnected and the induced subgraph formed by the other subset is the complement of a disconnected graph. Skew partitions play an important role in the theory of perfect graphs.
Definition A skew partition of a graph G {\displaystyle G} is a partition of its vertices into two subsets X {\displaystyle X} and Y {\displaystyle Y} for which the induced subgraph G [ X ] {\displaystyle G[X]} is disconnected and the induced subgraph G [ Y ] {\displaystyle G[Y]} is the complement of a disconnected graph (co-disconnected). Equivalently, a skew partition of a graph G {\displaystyle G} may be described by a partition of the vertices of G {\displaystyle G} into four subsets A {\displaystyle A} , B {\displaystyle B} , C {\displaystyle C} , and D {\displaystyle D} , such that there are no edges from A {\displaystyle A} to B {\displaystyle B} and such that all possible edges from C {\displaystyle C} to D {\displaystyle D} exist; for such a partition, the induced subgraphs G [ A ∪ B ] {\displaystyle G[A\cup B]} and G [ C ∪ D ] {\displaystyle G[C\cup D]} are disconnected and co-disconnected respectively, so we may take X = A ∪ B {\displaystyle X=A\cup B} and Y = C ∪ D {\displaystyle Y=C\cup D} .
Examples Every path graph with four or more vertices has a skew partition, in which the co-disconnected set Y {\displaystyle Y} is one of the interior edges of the path and the disconnected set X {\displaystyle X} consists of the vertices on either side of this edge. However, it is not possible for a cycle graph of any length to have a skew partition: no matter which subsets of the cycle are chosen as the set X {\displaystyle X} , the complementary set Y {\displaystyle Y} will have the same number of connected components, so it is not possible for X {\displaystyle X} to be disconnected and Y {\displaystyle Y} to be co-disconnected. If a graph has a skew partition, so does its complement. For instance, the complements of path graphs have skew partitions, and the complements of cycle graphs do not.
Special cases If a graph is itself disconnected, then with only three simple exceptions (an empty graph, a graph with one edge and three vertices, or a four-vertex perfect matching) it has a skew partition, in which the co-disconnected side of the partition consists of the endpoints of a single edge and the disconnected side consists of all other vertices. For the same reason, if the complement of a graph is disconnected, then with a corresponding set of three exceptions it must have a skew partition. If a graph has a clique separator (a clique whose removal would disconnect the remaining vertices) with more than one vertex, then the partition into the clique and the remaining vertices forms a skew partition. A clique cutset with one vertex is an articulation point; if such a vertex exists, then with a small number of simple exceptions, there is a skew partition in which the co-disconnected side consists of this vertex and one of its neighbors. A star cutset in a graph G {\displaystyle G} is a vertex separator in which one of the separator vertices is adjacent to all the others. Every clique separator is a star cutset. Necessarily, a graph with a star cutset (with more than one vertex) has a skew partition in which the co-disconnected subgraph consists of the vertices in the star cutset and the disconnected subgraph consists of all the remaining vertices. A module (or homogeneous set) is a nontrivial subset H {\displaystyle H} of the vertices of G {\displaystyle G} such that, for every vertex v {\displaystyle v} that is not in H {\displaystyle H} , either v {\displaystyle v} is adjacent to all vertices in H {\displaystyle H} or to none of them. If a graph G {\displaystyle G} has a module H {\displaystyle H} and, outside it, there exist both vertices adjacent to all vertices in H {\displaystyle H} and other vertices adjacent to none of them, then G {\displaystyle G} has a star cutset consisting of one vertex in the module together with its neighbors outside the module. On the other hand, if there exists a module in which one of these two subsets is empty, then the graph is disconnected or co-disconnected and again (with the three simple exceptions) it has a skew cutset.
… excerpt ends here. Continue reading the full article.
