Perfect matching cuts partitioning a graph into complementary subgraphs

DOI10.1007/978-3-031-06678-8_19OpenAlexW4285127765MaRDI QIDQ2169960

Erika M. M. Coelho, Hebert Coelho, Uéverton S. Souza, Diane Castonguay, Julliano Rosa Nascimento

Publication date: 30 August 2022

Full work available at URL: https://arxiv.org/abs/2210.06714

zbMATH Keywords

graph partitioningperfect matchinggraph isomorphismcomplementary subgraphsmatching cut

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Discrete mathematics in relation to computer science (68Rxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Recognizing some complementary products
• Partitioning extended \(P_4\)-laden graphs into cliques and stable sets
• Complexity properties of complementary prisms
• Algorithms solving the matching cut problem
• Complement reducible graphs
• 3-colorability \(\in \mathcal P\) for \(P_{6}\)-free graphs.
• Minimal separators in extended \(P_4\)-laden graphs
• Maximum induced matchings close to maximum matchings
• Decycling with a matching
• On the Cutwidth and the Topological Bandwidth of a Tree
• On testing isomorphism of permutation graphs
• Graphs in which some and every maximum matching is uniquely restricted
• Remarks on k-Clique, k-Independent Set and 2-Contamination in Complementary Prisms
• Partitioning a graph into complementary subgraphs

This page was built for publication: Perfect matching cuts partitioning a graph into complementary subgraphs