Destroying Bicolored $P_3$s by Deleting Few Edges

Niels Grüttemeier, Christian Komusiewicz, Jannik Schestag +1

We introduce and study the Bicolored $P_3$ Deletion problem defined as follows. The input is a graph $G=(V,E)$ where the edge set $E$ is partitioned into a set $E_r$ of red edges a…