Skew partition

A skew partition of a chordal graph. On the left side of the partition, the top and bottom parts are disconnected from each other. On the right side of the partition, all possible edges from top to bottom exist, forming a graph whose complement is disconnected.

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$ is a partition of its vertices into two subsets $X$ and $Y$ for which the induced subgraph $G[X]$ is disconnected and the induced subgraph $G[Y]$ is the complement of a disconnected graph (co-disconnected). Equivalently, a skew partition of a graph $G$ may be described by a partition of the vertices of $G$ into four subsets $A$, $B$, $C$, and $D$, such that there are no edges from $A$ to $B$ and such that all possible edges from $C$ to $D$ exist; for such a partition, the induced subgraphs $G[A\cup B]$ and $G[C\cup D]$ are disconnected and co-disconnected respectively, so we may take $X=A\cup B$ and $Y=C\cup D$.

Examples

Every path graph with four or more vertices has a skew partition, in which the co-disconnected set $Y$ is one of the interior edges of the path and the disconnected set $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$, the complementary set $Y$ will have the same number of connected components, so it is not possible for $X$ to be disconnected and $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.^[1]

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.^[1]

A star cutset in a graph $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.^[1]

A module (or homogeneous set) is a nontrivial subset $H$ of the vertices of $G$ such that, for every vertex $v$ that is not in $H$, either $v$ is adjacent to all vertices in $H$ or to none of them. If a graph $G$ has a module $H$ and, outside it, there exist both vertices adjacent to all vertices in $H$ and other vertices adjacent to none of them, then $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.^[1]

History

Skew partitions were introduced by Chvátal (1985), in connection with perfect graphs. Chvátal proved that a minimally imperfect graph could not have a star cutset. Trivially, disconnected graphs cannot be minimally imperfect, and it was also known that graphs with clique separators or modules could not be minimally imperfect.^[2] Claude Berge had conjectured in the early 1960s that perfect graphs were the same as the Berge graphs, graphs with no induced odd cycle (of length five or more) or its complement, and (because cycles and their complements do not have skew partitions) no minimal non-Berge graph can have a skew partition. Motivated by these results, Chvátal conjectured that no minimally imperfect graph could have a skew partition. Several authors proved special cases of this conjecture, but it remained unsolved for many years.^[3]

Skew partitions gained significance when they were used by Chudnovsky et al. (2006) to prove the strong perfect graph theorem that the Berge graphs are indeed the same as the perfect graphs. Chudnovsky et al. were unable to prove Chvátal's conjecture directly, but instead proved a weaker result, that a minimal counterexample to the theorem (if it existed) could not have a balanced skew partition, a skew partition in which every induced path with endpoints on one side of the partition and interior vertices on the other side has even length. This result formed a key lemma in their proof, and the full version of Chvátal's lemma follows from their theorem.^[4]

In structural graph theory

Skew partitions form one of the key components of a structural decomposition of perfect graphs used by Chudnovsky et al. (2006) as part of their proof of the strong perfect graph theorem. Chudnovsky et al. showed that every perfect graph either belongs to one of five basic classes of perfect graphs, or it has one of four types of decomposition into simpler graphs, one of which is a skew partition.

A simpler example of a structural decomposition using skew partitions is given by Seymour (2006). He observes that every comparability graph is complete, is bipartite, or has a skew partition. For, if every element of a partially ordered set is either a minimal element or a maximal element, then the corresponding comparability graph is bipartite. If the ordering is a total order, then the corresponding comparability graph is complete. If neither of these two cases arise, but every element that is neither minimal nor maximal is comparable to all other elements, then either the partition into the minimal and non-minimal elements (if there is more than one minimal element) or the partition into the maximal and non-maximal elements (if there is more than one maximal element) forms a star cutset. And in the remaining case, there exists an element $x$ of the partial order that is not minimal, not maximal, and not comparable with all other elements; in this case, there is a skew partition (the complement of a star cutset) in which the co-disconnected side consists of the elements comparable to $x$ (not including $x$ itself) and the disconnected side consists of the remaining elements.

The chordal graphs have an even simpler decomposition of a similar type: they are either complete or they have a clique separator. Hayward (1985) showed, analogously, that every connected and co-connected weakly chordal graph (a graph with no induced cycle or its complement of length greater than four) with four or more vertices has a star cutset or its complement, from which it follows by Chvátal's lemma that every such graph is perfect.

Algorithms and complexity

A skew partition of a given graph, if it exists, may be found in polynomial time. This was originally shown by de Figueiredo et al. (2000) but with an impractically large running time of $O(n^{101})$, where $n$ is the number of vertices in the input graph. Kennedy & Reed (2008) improved the running time to $O(n^4m)$; here $m$ is the number of input edges.

It is NP-complete to test whether a graph contains a skew partition in which one of the parts of the co-disconnected side is independent.^[5] Testing whether a given graph contains a balanced skew partition is also NP-complete in arbitrary graphs, but may be solved in polynomial time in perfect graphs.^[6]

Notes

1. Reed (2008).
2. Reed (2008). The nonexistence of modules in minimally imperfect graphs was used by Lovász (1972) in his proof of the weak perfect graph theorem.
3. See Cornuéjols & Reed (1993) for the case in which the co-disconnected side of the partition is multipartite, and Roussel & Rubio (2001) for the case in which one of the two parts of the co-disconnected side is independent.
4. Seymour (2006).
5. Dantas et al. (2004).
6. Trotignon (2008).

References

• Chudnovsky, Maria; Robertson, Neil; Seymour, Paul; Thomas, Robin (2006), "The strong perfect graph theorem", Annals of Mathematics, 164 (1): 51–229, doi:10.4007/annals.2006.164.51.
• Chvátal, V. (1985), "Star-cutsets and perfect graphs", Journal of Combinatorial Theory, Series B, 39 (3): 189–199, doi:10.1016/0095-8956(85)90049-8, MR 815391.
• Cornuéjols, G.; Reed, B. (1993), "Complete multi-partite cutsets in minimal imperfect graphs", Journal of Combinatorial Theory, Series B, 59 (2): 191–198, doi:10.1006/jctb.1993.1065, MR 1244930.
• Dantas, Simone; de Figueiredo, Celina M. H.; Klein, Sulamita; Gravier, Sylvain; Reed, Bruce A. (2004), "Stable skew partition problem", Discrete Applied Mathematics, 143 (1-3): 17–22, doi:10.1016/j.dam.2004.01.001, MR 2087864.
• de Figueiredo, Celina M. H.; Klein, Sulamita; Kohayakawa, Yoshiharu; Reed, Bruce A. (2000), "Finding skew partitions efficiently", Journal of Algorithms, 37 (2): 505–521, doi:10.1006/jagm.1999.1122, MR 1788847.
• Hayward, Ryan B. (1985), "Weakly triangulated graphs", Journal of Combinatorial Theory, Series B, 39 (3): 200–208, doi:10.1016/0095-8956(85)90050-4, MR 815392.
• Kennedy, William S.; Reed, Bruce (2008), "Fast skew partition recognition", Computational Geometry and Graph Theory: International Conference, KyotoCGGT 2007, Kyoto, Japan, June 11–15, 2007, Revised Selected Papers, Lecture Notes in Computer Science, 4535, Berlin: Springer, pp. 101–107, doi:10.1007/978-3-540-89550-3_11, MR 2672388.
• Lovász, László (1972), "Normal hypergraphs and the perfect graph conjecture", Discrete Mathematics, 2 (3): 253–267, doi:10.1016/0012-365X(72)90006-4.
• Reed, Bruce (2008), "Skew partitions in perfect graphs" (PDF), Discrete Applied Mathematics, 156 (7): 1150–1156, doi:10.1016/j.dam.2007.05.054, MR 2404228.
• Roussel, F.; Rubio, P. (2001), "About skew partitions in minimal imperfect graphs", Journal of Combinatorial Theory, Series B, 83 (2): 171–190, doi:10.1006/jctb.2001.2044, MR 1866394.
• Seymour, Paul (2006), "How the proof of the strong perfect graph conjecture was found" (PDF), Gazette des Mathématiciens (109): 69–83, MR 2245898.
• Trotignon, Nicolas (2008), "Decomposing Berge graphs and detecting balanced skew partitions", Journal of Combinatorial Theory, Series B, 98 (1): 173–225, doi:10.1016/j.jctb.2007.07.004, MR 2368032.