Oblique partition

Oblique partition of a chordal graph . On the left side of the partition, the lower and upper parts are not connected to each other. On the right side of the partition, all possible edges between the lower and upper parts exist, forming a graph whose complement is disconnected.

A skew partition of a graph is a partition of its vertices into two subsets, such that the generated subgraph formed by one of its subsets of vertices is disconnected , and the other generated subgraph formed by the other subset is a complement to the disconnected graph. Oblique partitions play an important role in the theory of perfect graphs .

Content

Definition

Oblique partition of the graph $G$ ${\ displaystyle G}$ Is a decomposition of the graph vertices into two subsets $X$ ${\ displaystyle X}$ and $Y$ ${\ displaystyle Y}$ for which the generated subgraph $G[X]$ ${\ displaystyle G [X]}$ disconnected, and the generated subgraph $G[Y]$ ${\ displaystyle G [Y]}$ is a complement to a disconnected graph (we will call it co-disconnected below). Equivalent, oblique graph partition $G$ ${\ displaystyle G}$ can be described as a partition of graph vertices $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}$ at $B$ ${\ displaystyle B}$ and such that all possible edges from $C$ ${\ displaystyle C}$ at $D$ ${\ displaystyle D}$ exist. For such a partition, the generated subgraphs $G[A\cup B]$ ${\ displaystyle G [A \ cup B]}$ and $G[C\cup D]$ ${\ displaystyle G [C \ cup D]}$ incoherent and co-incoherent respectively, so that we can take $X=A\cup B$ ${\ displaystyle X = A \ cup B}$ and $Y=C\cup D$ ${\ displaystyle Y = C \ cup D}$ .

Examples

Any path with four or more vertices has a skew partition, in which a co-disconnected set $Y$ ${\ displaystyle Y}$ is one of the inner edges of the path, and a disconnected set $X$ ${\ displaystyle X}$ consists of both vertices of this edge. However, it is impossible for loops of any length to have an oblique partition - it does not matter which subsets of loops are chosen as the set $X$ ${\ displaystyle X}$ additions to the set $Y$ ${\ displaystyle Y}$ will have the same number of connected components, so it's impossible $X$ ${\ displaystyle X}$ spread out and to $Y$ ${\ displaystyle Y}$ was co-incoherent.

If a graph has a skew partition, it has such a partition and its complement . For example, additions to paths have oblique partitions, and additions to loops do not.

Special Cases

If the graph is disconnected, then with the exception of three simple cases (an empty graph, a graph with one edge and three vertices, or a perfect matching at four vertices), it has an oblique partition, in which the co-disconnected side of the partition consists of endpoints of one edge and the disconnected side consists of from all the other peaks. For the same reason, if the complement of a graph is disconnected, then, with the exception of the corresponding set of three cases, it must have a skew partition ^[1] .

If the graph has a clique separator (a clique whose removal of which makes the remaining vertices disconnected) with more than one vertex, then the split into the clique and the remaining vertices forms an oblique split. A single vertex click section is a hinge . If such a vertex exists, then, with a few simple exceptions, there is an oblique partition in which the co-disconnected side consists of this vertex and one of its neighbors ^[1] .

Star section in graph $G$ ${\ displaystyle G}$ Is a vertex separator in which one of the vertices is adjacent to all other vertices of the separator. Any click separator is a stellar section. As necessary, a graph with a stellar section (with more than one vertex) has an oblique partition in which a co-disconnected subgraph consists of vertices of a stellar section, and a disconnected subgraph consists of all remaining vertices ^[1] .

A module (or a homogeneous set) is a nontrivial subset $H$ ${\ displaystyle H}$ vertices of the graph $G$ ${\ displaystyle G}$ such that for any vertex $v$ ${\ displaystyle v}$ not owned $H$ ${\ displaystyle H}$ either $v$ ${\ displaystyle v}$ adjacent to all the peaks in $H$ ${\ displaystyle H}$ or none of them. If the graph $G$ ${\ displaystyle G}$ has a module $H$ ${\ displaystyle H}$ and outside it there are peaks adjacent to all peaks $H$ ${\ displaystyle H}$ , and other vertices outside it are not adjacent to any vertex from $H$ ${\ displaystyle H}$ then $G$ ${\ displaystyle G}$ has a stellar section consisting of one vertex in a module together with its neighbors outside the module. On the other hand, if there is a module in which one of these two subsets is empty, then the graph is disconnected or co-disconnected and again (with the exception of three simple cases) it has an oblique section ^[1] .

History

Slanting partitions were introduced by Khvatal ^[2] in connection with perfect graphs . Enough proved that a minimally imperfect graph cannot have a stellar section. It is clear that disconnected graphs cannot be minimally imperfect, and it was also known that graphs with click separators or modules cannot be minimally imperfect ^[3] . Claudie Berge hypothesized in the early 1960s that perfect graphs should be the same as Berge graphs, graphs without an odd cycle (five or more lengths) or its complement, and (since cycles and their complement do not have skew partitions) no graph that is not a minimal Berge graph cannot have an oblique partition. Interested in these results, Khvatal hypothesized that no minimal imperfect graph can mark an oblique partition. Some authors have proved special cases of this hypothesis, but it has remained unresolved for a long time ^[4] .

Oblique partitions were especially important when they were used by Chudnovskaya, Robertson, Seymour and Thomas ^[5] to prove the strong theorem on perfect graphs that Berge graphs are the same as perfect graphs. Chudnovskaya and her group could not directly prove the Khvatal hypothesis, but they proved a weaker result that a minimal counterexample to the theorem (if such existed) would have to have a balanced oblique decomposition in which each generated path with an end on one side of the decomposition and internal vertices on the other side has an even length. This result has become a key lemma in their proof, and the full version of the Khvatal lemma follows from their theorem ^[6] .

In structural graph theory

Oblique partitions form a key component of the structural decomposition of perfect graphs, which was used by Chudnovskaya, Robertson, Seymour and Thomas ^[5] as part of the proof of the strong perfect graph theorem. Chudnovskaya et al. Showed that any perfect graph either belongs to five base classes of perfect graphs, or has one of four types of decomposition into simpler graphs, and one of these decompositions is skew decomposition.

A simple example of structural decomposition using oblique partitions was given by Seymour ^[6] . He noted that any graph of comparability is complete or bipartite or has a skew partition. Indeed, if any element of a partially ordered set is either a minimal element or a maximum element, then the corresponding comparability graph is bipartite. If the ordering is complete , then the corresponding graph of comparability is complete. If none of these cases takes place, but any element that is neither minimal nor maximum is comparable with all other elements, then either a partition into minimal and not minimal elements (if there is more than one minimal element), or a partition into maximum and non-maximum elements (if there is more than one maximum element) forms a stellar section. In the remaining case, there is an element $x$ ${\ displaystyle x}$ partial order, which is neither minimal nor maximum and is not comparable with all other elements. In this case, there is an oblique partition (complement of the stellar section), in which the co-disconnected side consists of elements comparable to $x$ ${\ displaystyle x}$ (not including myself $x$ ${\ displaystyle x}$ ), and the incoherent side consists of the remaining elements.

Chordal graphs have even simpler decompositions of a similar form - they are either complete or have a click separator. Hayward ^[7] showed similarly that any connected and co-connected weak chordal graph (a graph with a generated cycle of length more than four or its complement) with four or more vertices has a stellar section or its complement, whence it follows from the Hvatal lemma that any such Count is perfect.

Algorithms and Complexity

An oblique partition of a given graph, if exists, can be found in polynomial time . This was originally shown by Figueiredo, Klein, Kohayakawa and Reed ^[8] but with a very long run time $O(n^{101})$ ${\ displaystyle O (n ^ {101})}$ where $n$ ${\ displaystyle n}$ - the number of vertices of the input graph. Kennedy and Reed ^[9] improved the run time to $O(n^{4}m)$ ${\ displaystyle O (n ^ {4} m)}$ . Here $m$ ${\ displaystyle m}$ Is the number of edges.

The task of checking whether a graph contains a skew partition, in which one of the parts of the co-disconnected side is independent, is an NP-complete problem ^[10] . Checking whether a given graph contains a balanced oblique partition is also an NP-complete problem for arbitrary graphs, but the problem can be solved in polynomial time for perfect graphs ^[11] .

Notes

↑ ¹ ² ³ ⁴ Reed, 2008 .
↑ Chvátal, 1985 .
↑ Reed (2008 ). The non-existence of modules in minimal imperfect graphs was used by Lovas Lovász (1972 ) to prove the weak theorem on perfect graphs .
↑ See the article Cornuéjols, Reed (1993 ) for the case in which the co-disconnected side of the partition consists of several parts, and Roussel, Rubio (2001 ) for the case in which one of the two parts of the co-disconnected side is independent.
↑ ¹ ² Chudnovsky, Robertson, Seymour, Thomas, 2006 .
↑ ¹ ² Seymour, 2006 .
↑ Hayward, 1985 .
↑ de Figueiredo, Klein, Kohayakawa, Reed, 2000 .
↑ Kennedy, Reed, 2008 .
↑ Dantas, de Figueiredo, Klein, Gravier, Reed, 2004 .
↑ Trotignon, 2008 .

Literature

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

[_7c000d25c2c20393-1] ¹ ² ³ ⁴ Reed, 2008 .

[_928ff3a99b207aa6-2] Chvátal, 1985 .

[3] Reed (2008 ). The non-existence of modules in minimal imperfect graphs was used by Lovas Lovász (1972 ) to prove the weak theorem on perfect graphs .

[4] See the article Cornuéjols, Reed (1993 ) for the case in which the co-disconnected side of the partition consists of several parts, and Roussel, Rubio (2001 ) for the case in which one of the two parts of the co-disconnected side is independent.

[_812911d6784795f3-5] ¹ ² Chudnovsky, Robertson, Seymour, Thomas, 2006 .

[_c0ba88e742f0b65f-6] ¹ ² Seymour, 2006 .

[_b7a692f21ef51428-7] Hayward, 1985 .

[_af34002844b4be9b-8] Figueiredo, Klein, Kohayakawa, Reed, 2000 .

[_6225e2455fab33c5-9] Kennedy, Reed, 2008 .

[_788bc5493e21371b-10] Dantas, de Figueiredo, Klein, Gravier, Reed, 2004 .

[_e744f35f59e7b199-11] Trotignon, 2008 .