Decomposing Berge graphs and detecting balanced skew partitions

DOI10.1016/J.JCTB.2007.07.004zbMATH Open1131.05046arXiv1309.1960OpenAlexW2020405408MaRDI QIDQ2464161FDOQ2464161

Authors: Nicolas Trotignon 

Publication date: 10 December 2007

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

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.

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

Recommendations

• Berge trigraphs
• Publication:4508373
• 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

zbMATH Keywords

decomposition2-joinperfect graphrecognitiondetectionbalanced skew partitionBerge graph

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (13)

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

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)