Maximizing Matching Cuts

December 20, 2023 · The Ethereal · 🏛 arXiv.org

"No code URL or promise found in abstract"

Evidence collected by the PWNC Scanner

Authors Van Bang Le, Felicia Lucke, Daniël Paulusma, Bernard Ries arXiv ID 2312.12960 Category math.CO: Combinatorics Cross-listed cs.CC, cs.DM, cs.DS Citations 4 Venue arXiv.org Last Checked 2 months ago

Abstract

A matching cut in a graph G is an edge cut of G that is also a matching. This short survey gives an overview of old and new results and open problems for Maximum Matching Cut, which is to determine the size of a largest matching cut in a graph. We also compare this problem with the related problems Matching Cut, Minimum Matching Cut, and Perfect Matching Cut, which are to determine if a graph has a matching cut; the size of a smallest matching cut in a graph; and if a graph has a matching cut that is a perfect matching, respectively. Moreover, we discuss a relationship between Maximum Matching Cut and Max Cut, which is to determine the size of a largest edge cut in a graph, as well as a relationship between Minimum Matching Cut and Min Cut, which is to determine the size of a smallest edge cut in a graph.