Fast Skew Partition Recognition

DOI10.1007/978-3-540-89550-3_11MaRDI QIDQ5302744zbMATH OpenOpenAlexFDO

Authors W. Sean Kennedy, Bruce Reed

Publication date 13 January 2009

Published in Computational Geometry and Graph Theory (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-89550-3_11

Mathematics Subject Classification ID

Perfect graphs (05C17) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• scientific article; zbMATH DE number 1512686
• scientific article; zbMATH DE number 1545651
• Stable skew partition problem
• Colouring perfect graphs with bounded clique number
• Complexity of graph partition problems

Cites work

• Bull-free Berge graphs are perfect
• Compositions for perfect graphs
• Decomposing Berge graphs and detecting balanced skew partitions
• Decomposition by clique separators
• scientific article; zbMATH DE number 3168327 (Why is no real title available?)
• scientific article; zbMATH DE number 1455118 (Why is no real title available?)
• scientific article; zbMATH DE number 1545651 (Why is no real title available?)
• Skew partitions in perfect graphs
• Some properties of minimal imperfect graphs
• Star-cutsets and perfect graphs
• The strong perfect graph theorem

Cited in

(15)

• \(2K_2\)-partition of some classes of graphs
• The P versus NP-complete dichotomy of some challenging problems in graph theory
• The sandwich problem for decompositions and almost monotone properties
• The complexity of forbidden subgraph sandwich problems and the skew partition sandwich problem
• The computational complexity of disconnected cut and \(2 K_2\)-partition
• On the linear extension complexity of stable set polytopes for perfect graphs
• Graph partitions with prescribed patterns
• Skew partition sandwich problem is NP-complete
• Minimal disconnected cuts in planar graphs
• Colouring perfect graphs with bounded clique number
• Obstructions to partitions of chordal graphs
• scientific article; zbMATH DE number 1512686 (Why is no real title available?)
• scientific article; zbMATH DE number 1545651 (Why is no real title available?)
• The external constraint 4 nonempty part sandwich problem
• \(2K_{2}\) vertex-set partition into nonempty parts

This page was built for publication: Fast Skew Partition Recognition

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