Fast Skew Partition Recognition

DOI10.1007/978-3-540-89550-3_11zbMath1162.05359OpenAlexW143017274MaRDI QIDQ5302744

W. Sean Kennedy, Bruce A. 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

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

Related Items (13)

Colouring perfect graphs with bounded clique number ⋮ Obstructions to partitions of chordal graphs ⋮ Minimal Disconnected Cuts in Planar Graphs ⋮ The external constraint 4 nonempty part sandwich problem ⋮ The complexity of forbidden subgraph sandwich problems and the skew partition sandwich problem ⋮ \(2K_2\)-partition of some classes of graphs ⋮ The P versus NP-complete dichotomy of some challenging problems in graph theory ⋮ \(2K_{2}\) vertex-set partition into nonempty parts ⋮ The computational complexity of disconnected cut and \(2 K_2\)-partition ⋮ Graph partitions with prescribed patterns ⋮ The sandwich problem for decompositions and almost monotone properties ⋮ On the linear extension complexity of stable set polytopes for perfect graphs ⋮ Skew partition sandwich problem is NP-complete

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The strong perfect graph theorem
• Decomposition by clique separators
• Bull-free Berge graphs are perfect
• Star-cutsets and perfect graphs
• Some properties of minimal imperfect graphs
• Compositions for perfect graphs
• Decomposing Berge graphs and detecting balanced skew partitions
• Skew partitions in perfect graphs

This page was built for publication: Fast Skew Partition Recognition