Decomposing Berge graphs and detecting balanced skew partitions

DOI10.1016/J.JCTB.2007.07.004MaRDI QIDQ2464161zbMATH OpenOpenAlexFDO

Authors Nicolas Trotignon

Publication date 10 December 2007

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1309.0680, https://arxiv.org/abs/1309.1960

zbMATH Keywords

2-joinbalanced skew partitionBerge graphdecompositiondetectionperfect graphrecognition

Mathematics Subject Classification ID

Perfect graphs (05C17) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: A {em net} is a graph consisting of a triangle $C$ and three more vertices, each of degree one and with its neighbour in $C$, and all adjacent to different vertices of $C$. We give a polynomial-time algorithm to test whether an input graph has an induced subgraph which is a subdivision of a net. Unlike many similar questions, this does not seem to be solvable by an application of the "three-in-a-tree" subroutine.

Review text

A hole in a graph is an induced cycle of order at least 4. A Berge graph has no odd holes in either itself or its complement. The author shows that the problem of deciding whether a graph has a balanced skew partition is NP-hard, but gives an \(O(n^9)\)-time algorithm for the same problem restricted to Berge graphs. The algorithm is not constructive; it only certifies whether a graph has a balanced skew partition or not. It relies on a new decomposition theorem for Berge graphs, which also implies that every Berge graph can be decomposed first by using only balanced skew partitions and then by using only 2-joins.

Recommendations

• Berge trigraphs
• scientific article; zbMATH DE number 1512686
• Decomposing Berge graphs containing no proper wheel, long prism or their complements
• Recognizing Berge graphs
• Decomposition of even-hole-free graphs with star cutsets and 2-joins

Cites work

• A \(max \{m, n \}\) algorithm for determining the graph H from its line graph G
• An Optimal Algorithm to Detect a Line Graph and Output Its Root Graph
• Berge trigraphs
• Bull-free Berge graphs are perfect
• Compositions for perfect graphs
• Decomposition of odd-hole-free graphs by double star cutsets and 2-joins
• Even-hole-free graphs part II: Recognition algorithm
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1545651 (Why is no real title available?)
• On the complexity of testing for odd holes and induced odd paths
• Recognizing Berge graphs
• Skew partitions in perfect graphs
• Square-free perfect graphs.
• Star-cutsets and perfect graphs
• The strong perfect graph theorem

Cited in

(13)

• About skew partitions in minimal imperfect graphs
• The complexity of forbidden subgraph sandwich problems and the skew partition sandwich problem
• A faster algorithm to recognize even-hole-free graphs
• Detecting 2-joins faster
• Recognizing Berge graphs
• Clique-stable set separation in perfect graphs with no balanced skew-partitions
• Perfect graphs with no balanced skew-partition are 2-clique-colorable
• Skew partition sandwich problem is NP-complete
• Colouring perfect graphs with bounded clique number
• Coloring perfect graphs with no balanced skew-partitions
• Fast Skew Partition Recognition
• Berge trigraphs
• Combinatorial optimization with 2-joins

This page was built for publication: Decomposing Berge graphs and detecting balanced skew partitions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2464161)