Stable skew partition problem

DOI10.1016/j.dam.2004.01.001zbMath1053.05058OpenAlexW2025282997MaRDI QIDQ1887035

Sylvain Gravier, Simone Dantas, Sulamita Klein, Bruce A. Reed, Celina M. Herrera de Figueiredo

Publication date: 23 November 2004

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2004.01.001

zbMATH Keywords

Perfect graphsComputational difficulty of problemsAnalysis of algorithms and problem complexitySkew partitionStructural graph theory

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorial aspects of partitions of integers (05A17) Graph theory (including graph drawing) in computer science (68R10) Perfect graphs (05C17)

Related Items

Digraph matrix partitions and trigraph homomorphisms, The polynomial dichotomy for three nonempty part sandwich problems, The polynomial dichotomy for three nonempty part sandwich problems, The external constraint 4 nonempty part sandwich problem

Cites Work

• Unnamed Item
• Unnamed Item
• The strong perfect graph theorem
• Star-cutsets and perfect graphs
• Complete multi-partite cutsets in minimal imperfect graphs
• On stable cutsets in graphs
• About skew partitions in minimal imperfect graphs
• Complexity of graph partition problems
• Recognizing decomposable graphs