English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Zendy Open

Presents the pdf analysis as premium feature

PDF Analysis

Insights

Presents the summarisation as premium feature

Summarisation

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the zaia usage as premium feature

ZAIA

Zendy Tools

Zendy Plus

Presents the access of premium content as premium feature

Premium Content

A hole in a graph is an induced cycle on at least four vertices. A graph isBerge if it has no odd hole and if its complement has no odd hole. In 2002,Chudnovsky, Robertson, Seymour and Thomas proved a decomposition theorem forBerge graphs saying that every Berge graph either is in a well understood basicclass, or has some kind of decomposition. Then, Chudnovsky proved strongertheorems. One of them restricts the allowed decompositions to 2-joins andbalanced skew partitions.  We prove that the problem of deciding whether a graph has a balanced skewpartition is NP-hard. We give an $O(n^9)$-time algorithm for the same problemrestricted to Berge graphs. Our algorithm is not constructive: it onlycertifies whether a graph has a balanced skew partition or not. It relies on anew decomposition theorem for Berge graphs that is more precise than thepreviously known theorems. Our theorem also implies that every Berge graph canbe decomposed in a first step by using only balanced skew partitions, and in asecond step by using only 2-joins. Our proof of this new theorem uses at anessential step one of the theorems of Chudnovsky.

Decomposing Berge graphs and detecting balanced skew partitions