Conflict-Free Cuts in Planar and 3-Degenerate Graphs with 1-Regular Conflicts

Subrahmanyam Kalyanasundaram, Subodh Kumar

A conflict-free cut $F$ on a simple connected graph $G=(V,E)$ is defined as a set of edges $F\subseteq E$ such that $G-F$ is disconnected, and no two edges in $F$ are conflicti…