Finding d-Cuts in Probe H-Free Graphs
摘要
For an integer \(d\ge 1\) , the \(d\) -Cut problem is that of deciding whether a graph has an edge cut in which each vertex is adjacent to at most d vertices on the opposite side of the cut. The 1-Cut problem is the well-known Matching Cut problem. The \(d\) -Cut problem has been extensively studied for H-free graphs. We extend these results to the probe graph model, where we do not know all the edges of the input graph. For a graph H, a partitioned probe H-free graph (G, P, N) consists of a graph \(G=(V,E)\) , together with a set \(P\subseteq V\) of probes and an independent set \(N=V\setminus P\) of non-probes such that we can change G into an H-free graph by adding zero or more edges between vertices in N. For every graph H and every integer \(d\ge 1\) , we completely determine the complexity of \(d\) -Cut on partitioned probe H-free graphs.