2K₂ vertex-set partition into nonempty parts

DOI10.1016/J.DISC.2009.11.030MaRDI QIDQ966027zbMATH OpenOpenAlexFDO

Authors Kathryn Cook, Simone Dantas, Sulamita Klein, Elaine M. Eschen, Luerbio Faria, Celina M. H. de Figueiredo

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 complexityfixed-parameter algorithmsgraph algorithmscombinatorial problemsstructural graph theory

Mathematics Subject Classification ID

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

Recommendations

• 2K2 vertex-set partition into nonempty parts
• \(2K_2\)-partition of some classes of graphs
• 2K2-Partition Problem
• Degree-constrained 2-partitions of graphs
• The Complexity of the List Partition Problem for Graphs

Cites work

• scientific article; zbMATH DE number 1545651 (Why is no real title available?)
• 2K2-Partition Problem
• A tree representation for \(P_ 4\)-sparse graphs
• Fast Skew Partition Recognition
• FindingH-partitions efficiently
• Generalized colouring (matrix partitions) of cographs
• List Partitions
• List homomorphisms to reflexive graphs
• List matrix partitions of chordal graphs
• Matrix partitions of perfect graphs
• 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
• The strong perfect graph theorem

Cited in

(11)

• Disconnected cuts in claw-free graphs
• Disconnected cuts in claw-free graphs
• Graph partitions with prescribed patterns
• The complexity of surjective homomorphism problems-a survey
• The computational complexity of disconnected cut and \(2 K_2\)-partition
• The P versus NP-complete dichotomy of some challenging problems in graph theory
• The external constraint 4 nonempty part sandwich problem
• Degree-constrained 2-partitions of graphs
• \(2K_2\)-partition of some classes of graphs
• 2K2-Partition Problem
• 2K2 vertex-set partition into nonempty parts

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

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