6 papers · 1 filter
Perfect matching cuts partitioning a graph into complementary subgraphs
Diane Castonguay, Erika M. M. Coelho, Hebert Coelho +2
In Partition Into Complementary Subgraphs (Comp-Sub) we are given a graph , and an edge set property , and asked whether can be decomposed into two graphs, and…
Computing the Largest Bond and the Maximum Connected Cut of a Graph
Gabriel L. Duarte, Hiroshi Eto, Tesshu Hanaka +6
The cut-set of a graph is the set of edges that have one endpoint in and the other endpoint in , and whenever is connected…
Reducing graph transversals via edge contractions
Paloma T. Lima, Vinicius F. dos Santos, Ignasi Sau +1
For a graph invariant , the Contraction() problem consists in, given a graph and two positive integers , deciding whether one can contract at most edges of t…
Width Parameterizations for Knot-free Vertex Deletion on Digraphs
Stéphane Bessy, Marin Bougeret, Alan D. A. Carneiro +2
A knot in a directed graph is a strongly connected subgraph of with at least two vertices, such that no vertex in is an in-neighbor of a vertex in $V(G)\setminus…
Computing the largest bond of a graph
Gabriel L. Duarte, Daniel Lokshtanov, Lehilton L. C. Pedrosa +2
A bond of a graph is an inclusion-wise minimal disconnecting set of , i.e., bonds are cut-sets that determine cuts of such that and $G[V\setmin…
Maximum cuts in edge-colored graphs
Luerbio Faria, Sulamita Klein, Ignasi Sau +2
The input of the Maximum Colored Cut problem consists of a graph with an edge-coloring and a positive integer , and the question is wheth…