\(2K_{2}\) vertex-set partition into nonempty parts

DOI10.1016/j.disc.2009.11.030zbMath1230.05233OpenAlexW2097058112MaRDI QIDQ966027

Sulamita Klein, Kathryn Cook, Simone Dantas, Celina M. Herrera de Figueiredo, Elaine M. Eschen, Luérbio Faria

Publication date: 27 April 2010

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

Full work available at URL: https://doi.org/10.1016/j.disc.2009.11.030

zbMATH Keywords

computational complexitycombinatorial problemsgraph algorithmsfixed-parameter algorithmsstructural graph theory

Mathematics Subject Classification ID

Partitions of sets (05A18) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (7)

Disconnected cuts in claw-free graphs ⋮ Unnamed Item ⋮ The complexity of surjective homomorphism problems-a survey ⋮ The external constraint 4 nonempty part sandwich problem ⋮ The P versus NP-complete dichotomy of some challenging problems in graph theory ⋮ The computational complexity of disconnected cut and \(2 K_2\)-partition ⋮ Graph partitions with prescribed patterns

Cites Work

• Unnamed Item
• Unnamed Item
• List matrix partitions of chordal graphs
• The strong perfect graph theorem
• List homomorphisms to reflexive graphs
• A tree representation for \(P_ 4\)-sparse graphs
• Matrix partitions of perfect graphs
• 2K2-Partition Problem
• The Complexity of the List Partition Problem for Graphs
• The Complexity of the Partial Order Dimension Problem
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• List Partitions
• FindingH-partitions efficiently
• Fast Skew Partition Recognition

This page was built for publication: \(2K_{2}\) vertex-set partition into nonempty parts