2K₂ vertex-set partition into nonempty parts

DOI10.1016/J.DISC.2009.11.030zbMATH Open1230.05233OpenAlexW2097058112MaRDI QIDQ966027FDOQ966027

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

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

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)

Cites Work

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

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)