Perfect matching cuts partitioning a graph into complementary subgraphs
Graph designs and isomorphic decomposition (05C51) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph operations (line graphs, products, etc.) (05C76) Graph algorithms (graph-theoretic aspects) (05C85)
Lately, making graph partitions with particular attributes is a topic of extensive research. In partition into complementary subgraphs (COMP-SUB) given a graph \(G = (V, E)\), and an edge set property \(\Pi\) the question is whether \(G\) can be decomposed into two graphs, \(H\) and its complement \(\overline{H}\), for some graph \(H\), in such a way that the edge cut \([V(H), V(\overline{H})]\) satisfies the property \(\Pi\). The authors consider COMP-SUB\((\Pi)\) when the property \(\Pi = \mathscr{PM}\) specifies that the edge cut of the decomposition is a perfect matching and prove that COMP-SUB(PM) is GI-hard when the graph \(G\) is \(C_5\)-free or \(G\) is \(\{C_{k \geq 7}, \overline{C}_{k \geq 7}\}\)-free. They also show that COMP-SUB(PM) is polynomial-time solvable on hole-free graphs and \(P_5\)-free graphs and presented characterizations of COMP-SUB(PM) on chordal, distance-hereditary, and extended \(P_4\)-laden graphs. They conclude the article with open problems such as a) Can COMP-SUB(PM) on \(C_k\geq 6\)-free graphs be solved in polynomial time? b) What is the complexity of COMP-SUB(PM) on \(P_6\)-free graphs? c) Is COMP-SUB(PM) complete?
- 3-colorability \(\in \mathcal P\) for \(P_{6}\)-free graphs.
- Algorithms solving the matching cut problem
- Clique cycle transversals in graphs with few \(P_{4}\)'s
- Complement reducible graphs
- Complexity properties of complementary prisms
- Decycling a graph by the removal of a matching: new algorithmic and structural aspects in some classes of graphs
- Decycling with a matching
- Graph theory with applications
- Graphs in which some and every maximum matching is uniquely restricted
- scientific article; zbMATH DE number 1202982 (Why is no real title available?)
- scientific article; zbMATH DE number 2044946 (Why is no real title available?)
- Maximum induced matchings close to maximum matchings
- Minimal separators in extended \(P_4\)-laden graphs
- Modular decomposition and transitive orientation
- On testing isomorphism of permutation graphs
- On the computational complexity of the bipartizing matching problem
- On the Cutwidth and the Topological Bandwidth of a Tree
- Partitioning a graph into complementary subgraphs
- Partitioning extended \(P_4\)-laden graphs into cliques and stable sets
- Recognizing some complementary products
- Remarks on k-clique, k-independent set and 2-contamination in complementary prisms
- The complementary product of two graphs
This page was built for publication: Perfect matching cuts partitioning a graph into complementary subgraphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6996465)
