{"id":"arxiv/2605.12068","url":"https://arxiv.org/abs/2605.12068","tags":["math.CO"],"score":0,"title":"Conflict-Free Cuts in Planar and 3-Degenerate Graphs with 1-Regular Conflicts","domain":"math.CO","source":"arxiv","authors":["Subrahmanyam Kalyanasundaram","Subodh Kumar"],"reviews":0,"subject":"math.CO","summary":"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 conflicting. The notion of conflicting edges is represented using an associated conflict graph $\\widehat{G} = (\\widehat{V}, \\widehat{E})$ where $\\widehat{V} = E$. Deciding if a given planar graph $G$, with an associated conflict graph $\\widehat{G}$, has a conflict-free cut is known to be NP-complete, when $G$ has maximum degree four and $\\widehat{G}$ is a line graph of $G$ [Bonsma, JGT 2009]. In this paper, we prove the…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-05-12","reactions":{}}