arxiv: 2605.12068 · v1 · submitted 2026-05-12 · 🧮 math.CO

Recognition: 2 theorem links

· Lean Theorem

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

Subodh Kumar, Subrahmanyam Kalyanasundaram

Pith reviewed 2026-05-13 04:45 UTC · model grok-4.3

classification 🧮 math.CO

keywords conflict-free cutplanar graphs3-degenerate graphsNP-completeness1-regular conflict graphedge matchinggraph disconnection

0 comments

The pith

Every planar 4-regular graph except the octahedron admits a conflict-free cut when edge conflicts form disjoint pairs.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper shows that when edges of a graph are paired into conflicting pairs, any planar 4-regular graph other than the octahedron always has a disconnecting edge set that takes at most one edge from each pair. It proves that deciding whether such a set exists is NP-complete once the maximum degree rises to 5, both for planar graphs and for 3-degenerate graphs. The work also exhibits infinite families of graphs that possess no conflict-free cut at all under 1-regular conflicts. These statements settle the complexity status for the listed graph classes and separate the cases where existence is guaranteed from those where it must be computed.

Core claim

For any 1-regular conflict graph on the edges, every planar 4-regular graph other than the octahedron graph possesses a conflict-free cut. The decision problem of whether a conflict-free cut exists is NP-complete both for planar graphs of maximum degree 5 and for 3-degenerate graphs of maximum degree 5. Infinite families of graphs equipped with 1-regular conflict graphs that admit no conflict-free cut are constructed.

What carries the argument

A conflict-free cut: a disconnecting edge subset that contains at most one edge from each conflicting pair in the given 1-regular conflict graph on the edge set.

If this is right

Conflict-free cuts exist in every planar 4-regular graph except the octahedron.
Deciding existence of a conflict-free cut is NP-complete for planar graphs of maximum degree 5.
Deciding existence of a conflict-free cut is NP-complete for 3-degenerate graphs of maximum degree 5.
There exist infinite families of graphs with 1-regular conflicts that have no conflict-free cut whatsoever.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The degree-4 guarantee indicates that planarity plus regularity together force the existence of a constrained disconnecting set.
The jump to NP-completeness at degree 5 shows that one additional incident edge per vertex supplies enough freedom for hardness reductions while preserving planarity or 3-degeneracy.
Analogous thresholds may exist for other sparse classes such as bounded-treewidth or series-parallel graphs.

Load-bearing premise

The conflicts between edges form a perfect matching of disjoint pairs.

What would settle it

A planar 4-regular graph distinct from the octahedron together with a 1-regular conflict assignment on its edges that admits no conflict-free cut would refute the existence claim.

Figures

Figures reproduced from arXiv: 2605.12068 by Subodh Kumar, Subrahmanyam Kalyanasundaram.

**Figure 1.** Figure 1: Uncuttable octahedron with 1-regular conflicts. We give an overview of the proof. We first show that the planar embedding must contain faces that do not have conflicts between adjacent edges. If such a face is a triangle, we reason that there is always a CF-cut unless the graph is an octahedron. Otherwise, we can separate the face from the rest of the graph unless there are two conflicting edges that con… view at source ↗

**Figure 2.** Figure 2: (a) CF triangle without conflicts (b) CF triangle with one out of eight [PITH_FULL_IMAGE:figures/full_fig_p007_2.png] view at source ↗

**Figure 3.** Figure 3: (a) CF triangle with all T1 conflicts (b) CF triangle with all T2 conflicts The case when e2 conflicts with e5 or the case when e9 conflicts with e5 results in a CF-cut due to Observation 13. Therefore, the only thing that remains is e2 conflicting with e9, as shown in Figure 4a. We analyse it based on subcases. Let us assume that the edges e2 and e9 meet at a vertex v4 and we further assume that the other… view at source ↗

**Figure 4.** Figure 4: (a) Case 3 of Lemma 9. (b) Case 4 of Lemma 9. [PITH_FULL_IMAGE:figures/full_fig_p009_4.png] view at source ↗

**Figure 5.** Figure 5: e10 conflicts with e5 v1 v2 v3 v4 v5 e1 e7 e4 e9 e2 e11 e3 e5 e6 e8 e10 [PITH_FULL_IMAGE:figures/full_fig_p010_5.png] view at source ↗

**Figure 7.** Figure 7: (a) Incomplete Octahedron (b) Uncuttable Octahedron [PITH_FULL_IMAGE:figures/full_fig_p011_7.png] view at source ↗

**Figure 10.** Figure 10 [PITH_FULL_IMAGE:figures/full_fig_p011_10.png] view at source ↗

**Figure 8.** Figure 8: (a) e10 conflicts with e6 (b) Incomplete uncuttable octahedron when e10 conflicts with e6 Let us assume that the edges e11 and e6 meet at the vertex v5. Notice that e5 cannot be parallel to e4 or e6, and the only other possibility is that it ends at a new vertex contained in the region bounded by the cycle e2, e11, e6, e4. But then, all the vertices inside this cycle can be separated from the rest of the g… view at source ↗

**Figure 9.** Figure 9: Uncuttable octahedron in the case when e10 and e6 mutually conflict. v1 v2 v3 v4 v5 e1 e7 e4 e9 e2 e11 e3 e6 e5 e8 e10 [PITH_FULL_IMAGE:figures/full_fig_p012_9.png] view at source ↗

**Figure 11.** Figure 11: CF-cuts when vivj , |j − i| mod ℓ ≥ 2, is an edge on a CF face in G Let vi−1vivi+1 . . . vj−1vjvj+1 be a path along the CF face F. Let the edge vivj be conflicting with the edge vivi+1. Let the other edge incident with vi be viy and that on vj be vj z. By Observation 7, it follows that the edge vj z will conflict with the edge vjvj+1. We may observe here that the vertices L = vivi+1 . . . vj−1vjvi [PITH_… view at source ↗

**Figure 12.** Figure 12: (a) Case 1.1 of Lemma 11 (b) Case 1.2 of Lemma 11 [PITH_FULL_IMAGE:figures/full_fig_p015_12.png] view at source ↗

**Figure 13.** Figure 13: (a) Case 1.3 of Lemma 11, and (b) Case 1.4 of Lemma 11 [PITH_FULL_IMAGE:figures/full_fig_p015_13.png] view at source ↗

**Figure 14.** Figure 14: (a) Case 2.1 of Lemma 11 (b) Case 2.2 of Lemma 11 [PITH_FULL_IMAGE:figures/full_fig_p016_14.png] view at source ↗

**Figure 15.** Figure 15: (a) Case 2.3 of Lemma 11, and (b) Case 2.4 of Lemma 11 [PITH_FULL_IMAGE:figures/full_fig_p016_15.png] view at source ↗

**Figure 16.** Figure 16: (a) Case 3.1 of Lemma 11 (b) Case 3.2 of Lemma 11 [PITH_FULL_IMAGE:figures/full_fig_p017_16.png] view at source ↗

**Figure 17.** Figure 17: (a) Case 3.3 of Lemma 11, and (b) Case 3.4 of Lemma 11 [PITH_FULL_IMAGE:figures/full_fig_p017_17.png] view at source ↗

**Figure 18.** Figure 18: A CF face protected by a CFFPT We first note that there cannot be CFFPTs on two consecutive boundary edges of F. This is due to the Lemma 7, which says one incident edge on each vi must conflict with a boundary edge of F either in a clockwise way or in an anticlockwise way. Throughout this proof, we use the following notation of the vertices in G with respect to the CF face F. Note that this may neither b… view at source ↗

**Figure 19.** Figure 19: Case 1.1 of Lemma 12. The CF-cut in each case is shown in red. [PITH_FULL_IMAGE:figures/full_fig_p021_19.png] view at source ↗

**Figure 20.** Figure 20: Case 1.2 of Lemma 12 [PITH_FULL_IMAGE:figures/full_fig_p022_20.png] view at source ↗

**Figure 21.** Figure 21: Case 1.3 of Lemma 12. The CF-cut in each case is shown in red. [PITH_FULL_IMAGE:figures/full_fig_p023_21.png] view at source ↗

**Figure 22.** Figure 22: Case 2.1 of Lemma 12. The CF-cut in each case is shown in red. [PITH_FULL_IMAGE:figures/full_fig_p024_22.png] view at source ↗

**Figure 23.** Figure 23: Case 2.2 of Lemma 12 [PITH_FULL_IMAGE:figures/full_fig_p025_23.png] view at source ↗

**Figure 24.** Figure 24: Case 2.3 of Lemma 12. The CF-cut in each case is shown in red. [PITH_FULL_IMAGE:figures/full_fig_p026_24.png] view at source ↗

**Figure 25.** Figure 25: Case 3 of Lemma 12. The CF-cuts are shown in red. [PITH_FULL_IMAGE:figures/full_fig_p028_25.png] view at source ↗

**Figure 26.** Figure 26: The variable gadget representing the three literals of the variable xi. The parallel edges ui,2vi,2 represent the negated literal and the edges ui,1vi,1, ui,3vi,3 represent the positive literals. Dashed edges represent conflicts. x1, x¯3 x¯2, x3 x¯1, x2, x3 x1, x2 s x1 x2 x3 t [PITH_FULL_IMAGE:figures/full_fig_p030_26.png] view at source ↗

**Figure 28.** Figure 28: (a) Square of C2n (n = 6) with 1-regular conflict. Dashed edges represent conflicts. (b) Square of C2n when modified into He2n. Sub-Case 1.1 (i + 2 ∈ A): Let (i + 2) ∈ A. This means that the edge {(i + 1),(i+ 2)} does not belong to the CF-cut M but the edge {i ′ ,(i+ 2)} does. This implies that the edge {i ′ ,(i+ 2)′}) ∈/ M and the vertex (i+ 2)′ ∈ B. Since, edges {(i + 2),(i + 3)} and {(i + 2),(i + 2)′} … view at source ↗

**Figure 29.** Figure 29: (a) An uncuttable, 3-degenerate graph H with 1-regular conflicts, (b) An uncuttable, 3-degenerate graph H′ derived from H after adding a vertex u1 and a pair of conflicting edges u1v1 and u1v2 to H. Dashed edges represent conflicts. Lemma 25. The graph H with 1-regular conflicts as shown in [PITH_FULL_IMAGE:figures/full_fig_p035_29.png] view at source ↗

**Figure 30.** Figure 30: (a) An uncuttable, extendable, 3-degenerate graph Hi for i = 1, of max degree 5 with 1-regular conflicts, (b) An uncuttable, extendable, 3-degenerate graph Hi for i = 2, of max degree 5. The dotted lines represent the conflicts. Now we are ready to prove Theorem 24. Proof (Proof of Theorem 24). It is straightforward to see that the problem is in NP since we only need to verify that a given cut M separates… view at source ↗

**Figure 31.** Figure 31: (a) Prism Graph on 4t vertices for t = 2 with 1-regular conflicts and (b) Prism Graph on 4t vertices for t = 3 with 1-regular conflicts. The main result of this section is stated below. Theorem 28. Let G = P ∗ 4t be the planar dual of the prism graph on 4t vertices, where t ≥ 2. There exists a 1-regular conflict graph Gb for which the graph G does not have a conflict-free cut [PITH_FULL_IMAGE:figures/ful… view at source ↗

**Figure 32.** Figure 32: (a) Subgraph H with 1-regular conflicts and (b) Subgraph H′ with 1-regular conflicts. Lemma 30. Let t ≥ 2. Using subgraphs H and H′ with 1-regular conflicts, as shown in [PITH_FULL_IMAGE:figures/full_fig_p039_32.png] view at source ↗

read the original abstract

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 following for the case when $\widehat{G}$ is 1-regular. * We completely resolve the complexity of the decision problem when $G$ is planar. Towards this end, we show that (a) there always exists a conflict-free cut when the graph is planar and 4-regular unless it is the octahedron graph and (b) the decision problem is NP-complete, even in the case when $G$ is planar with maximum degree 5. * We also show that the decision problem is NP-complete when $G$ is a 3-degenerate graph with maximum degree 5. This completely resolves the complexity status of the problem when $G$ is 3-degenerate. * We construct families of graphs with 1-regular conflict graphs that do not have a conflict-free cut. Our results answer the questions posed in [Rauch, Rautenbach and Souza, IPL 2025].

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper settles the complexity status for conflict-free cuts in planar and 3-degenerate graphs under exactly 1-regular conflicts.

read the letter

The main thing to know is that the authors prove an existence theorem for planar 4-regular graphs (a conflict-free cut always exists except on the octahedron) and show the decision problem is NP-complete for planar graphs of maximum degree 5 and for 3-degenerate graphs of maximum degree 5, all when the conflict graph is 1-regular. This directly answers the open questions left in Rauch, Rautenbach and Souza's 2025 IPL paper and extends Bonsma's 2009 hardness result for line graphs to this paired-conflict setting. They also construct explicit families of graphs with 1-regular conflicts that have no conflict-free cut at all. These are clean, targeted results that close the complexity picture for two natural graph families. The positive existence statement stands out because it gives a structural guarantee rather than just another hardness proof. The reductions are asserted to preserve planarity and 3-degeneracy while keeping the conflict graph exactly 1-regular and the maximum degree at 5, which is the right level of care for this kind of work. One soft spot is that the abstract supplies no proof sketches or gadget diagrams, so the soundness of the reductions cannot be checked from the summary alone. If the full paper contains careful verification that the gadgets do not accidentally raise degrees or create extra conflicts, the concern is minor; otherwise it would need tightening. There is no circularity or reliance on fitted parameters here. The work is for people who study constrained cuts, planar graph algorithms, and NP-completeness in sparse or degenerate graphs. A reader who already knows the 2025 IPL questions will get immediate value from the resolution. It deserves a serious referee because the claims are precise, the prior literature is properly cited, and the results are independent of self-referential loops. I would send it out for review.

Referee Report

0 major / 3 minor

Summary. The manuscript studies conflict-free cuts (edge sets whose removal disconnects the graph with no two edges conflicting) under the restriction that the conflict graph is exactly 1-regular. It proves that every planar 4-regular graph admits a conflict-free cut except the octahedron; shows that deciding existence is NP-complete for planar graphs of maximum degree 5; proves NP-completeness for 3-degenerate graphs of maximum degree 5; and constructs infinite families of graphs with 1-regular conflicts that have no conflict-free cut. These results resolve the open questions left by Rauch, Rautenbach and Souza (IPL 2025).

Significance. If the proofs hold, the work completely settles the complexity status of the conflict-free cut problem for all planar graphs and all 3-degenerate graphs when conflicts are 1-regular. The structural existence theorem for 4-regular planar graphs is strong and clean, while the two NP-completeness results close the remaining cases left open by prior hardness proofs that used line graphs or unrestricted conflicts. The explicit constructions of graphs without conflict-free cuts supply concrete negative examples and boundary cases.

minor comments (3)

Abstract: a one-sentence indication of the main proof techniques (e.g., “by Eulerian orientation and matching arguments” or “by planar gadget reduction from 3-SAT”) would help readers gauge the approach without reading the full text.
The manuscript should include a small illustrative figure (perhaps in the construction section) showing one member of the infinite family of graphs without conflict-free cuts.
Ensure that the bibliographic entry for the 2025 IPL paper is complete and that all cross-references to prior work on line-graph conflicts are consistent.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive summary, significance assessment, and recommendation of minor revision. The report confirms that our results resolve the open questions from Rauch, Rautenbach and Souza (IPL 2025) for planar and 3-degenerate graphs under 1-regular conflicts. Since no specific major comments or requested changes were listed, we provide no point-by-point responses below.

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The paper establishes an existence theorem for conflict-free cuts in planar 4-regular graphs (except the octahedron) via direct case analysis and constructs explicit NP-completeness reductions for planar max-degree-5 and 3-degenerate max-degree-5 graphs using new gadgets that preserve the 1-regular conflict condition. These steps are self-contained mathematical arguments that do not reduce to prior fitted parameters, self-defined quantities, or load-bearing self-citations. The only external reference is to Rauch et al. (IPL 2025), which merely poses the open questions resolved here; no ansatz, uniqueness theorem, or renaming of known results is imported from overlapping authors. The derivation chain therefore stands on independent proofs and reductions.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The claims rest on standard definitions and properties of planar graphs, 3-degenerate graphs, and 1-regular graphs together with new reduction arguments; no free parameters, ad-hoc constants, or invented entities are introduced.

axioms (1)

standard math Standard definitions and basic properties of planar graphs, 3-degenerate graphs, and 1-regular graphs hold.
The paper invokes these established graph-theoretic notions without re-proving them.

pith-pipeline@v0.9.0 · 5621 in / 1360 out tokens · 96957 ms · 2026-05-13T04:45:11.994132+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Foundation/AlexanderDuality.lean alexander_duality_circle_linking unclear
We show that (a) there always exists a conflict-free cut when the graph is planar and 4-regular unless it is the octahedron graph and (b) the decision problem is NP-complete, even in the case when G is planar with maximum degree 5.
IndisputableMonolith/Foundation/ArithmeticFromLogic.lean LogicNat induction unclear
We also show that the decision problem is NP-complete when G is a 3-degenerate graph with maximum degree 5.

Reference graph

Works this paper leans on

20 extracted references · 20 canonical work pages

[1]

Conflict Free Feedback Vertex Set: A Parameterized Dichotomy

Akanksha Agrawal, Pallavi Jain, Lawqueen Kanesh, Daniel Lokshtanov, and Saket Saurabh. Conflict Free Feedback Vertex Set: A Parameterized Dichotomy. In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018), pages 53:1–53:15, Dagstuhl, Germany, 2018

work page 2018
[2]

Parame- terized complexity of conflict-free matchings and paths.Algorithmica, 82(7):1939– 1965, 2020

Akanksha Agrawal, Pallavi Jain, Lawqueen Kanesh, and Saket Saurabh. Parame- terized complexity of conflict-free matchings and paths.Algorithmica, 82(7):1939– 1965, 2020

work page 1939
[3]

On conflict-free spanning tree: Mapping tractable and hard instances through the lenses of graph classes.Theoretical Computer Science, 1031:115081, 2025

Bruno Jos´ e S Barros, Luiz Satoru Ochi, Rian G S Pinheiro, and U´ everton S Souza. On conflict-free spanning tree: Mapping tractable and hard instances through the lenses of graph classes.Theoretical Computer Science, 1031:115081, 2025

work page 2025
[4]

A branch-and-bound algorithm for the knapsack problem with conflict graph.INFORMS J

Andrea Bettinelli, Valentina Cacchiani, and Enrico Malaguti. A branch-and-bound algorithm for the knapsack problem with conflict graph.INFORMS J. on Com- puting, 29(3):457–473, August 2017

work page 2017
[5]

The complexity of the matching-cut problem for planar graphs and other graph classes.Journal of Graph Theory, 62(2):109–126, 2009

Paul Bonsma. The complexity of the matching-cut problem for planar graphs and other graph classes.Journal of Graph Theory, 62(2):109–126, 2009

work page 2009
[6]

Matching cut in graphs with large minimum degree.Algorithmica, 83(5):1238–1255, May 2021

Chi-Yeh Chen, Sun-Yuan Hsieh, Hoang-Oanh Le, Van Bang Le, and Sheng- Lung Peng. Matching cut in graphs with large minimum degree.Algorithmica, 83(5):1238–1255, May 2021

work page 2021
[7]

Recognizing decomposable graphs.Journal of Graph Theory, 8(1):51–53, 1984

Vasek Chv´ atal. Recognizing decomposable graphs.Journal of Graph Theory, 8(1):51–53, 1984

work page 1984
[8]

Hitting for- bidden subgraphs in graphs of bounded treewidth.Information and Computation, 256:62–82, 2017

Marek Cygan, D´ aniel Marx, Marcin Pilipczuk, and Micha l Pilipczuk. Hitting for- bidden subgraphs in graphs of bounded treewidth.Information and Computation, 256:62–82, 2017

work page 2017
[9]

Woeginger

Andreas Darmann, Ulrich Pferschy, Joachim Schauer, and Gerhard J. Woeginger. Paths, trees and matchings under disjunctive constraints.Discrete Appl. Math., 159(16):1726–1735, 2011

work page 2011
[10]

Graph theory 6th ed.Graduate texts in mathematics, 173, 2024

Reinhard Diestel. Graph theory 6th ed.Graduate texts in mathematics, 173, 2024

work page 2024
[11]

Online variable-sized bin packing with conflicts.Discrete Optimization, 8(2):333–343, 2011

Leah Epstein, Lene M Favrholdt, and Asaf Levin. Online variable-sized bin packing with conflicts.Discrete Optimization, 8(2):333–343, 2011

work page 2011
[12]

Matching cuts in graphs of high girth andH-free graphs.Algorithmica, 87(8):1199–1221, May 2025

Carl Feghali, Felicia Lucke, Dani¨ el Paulusma, and Bernard Ries. Matching cuts in graphs of high girth andH-free graphs.Algorithmica, 87(8):1199–1221, May 2025. 42 Subrahmanyam Kalyanasundaram and Subodh Kumar

work page 2025
[13]

Conflict-free hypergraph matchings.Journal of the London Mathematical Soci- ety, 109(5):e12899, 2024

Stefan Glock, Felix Joos, Jaehoon Kim, Marcus K¨ uhn, and Lyuben Lichev. Conflict-free hypergraph matchings.Journal of the London Mathematical Soci- ety, 109(5):e12899, 2024

work page 2024
[14]

Re- fined notions of parameterized enumeration kernels with applications to matching cut enumeration.J

Petr A Golovach, Christian Komusiewicz, Dieter Kratsch, and Van Bang Le. Re- fined notions of parameterized enumeration kernels with applications to matching cut enumeration.J. Comput. Syst. Sci., 123(C):76–102, February 2022

work page 2022
[15]

Bounds on multiprocessing anomalies and related packing algo- rithms

Ronald L Graham. Bounds on multiprocessing anomalies and related packing algo- rithms. InProceedings of the May 16-18, 1972, spring joint computer conference, pages 205–217, 1971

work page 1972
[16]

Conflict-free cuts in pla- nar and 3-degenerate1 graphs with 1-regular conflicts

Subrahmanyam Kalyanasundaram and Subodh Kumar. Conflict-free cuts in pla- nar and 3-degenerate1 graphs with 1-regular conflicts. InProceedings of the 37th International Workshop on Combinatorial Algorithms (IWOCA 2026), 2026

work page 2026
[17]

Matching cut: kernel- ization, single-exponential time FPT, and exact exponential algorithms.Discrete Applied Mathematics, 283:44–58, 2020

Christian Komusiewicz, Dieter Kratsch, and Van Bang Le. Matching cut: kernel- ization, single-exponential time FPT, and exact exponential algorithms.Discrete Applied Mathematics, 283:44–58, 2020

work page 2020
[18]

Dichotomies for maximum matching cut:H-freeness, bounded diameter, bounded radius.Theoretical Com- puter Science, 1017:114795, 2024

Felicia Lucke, Dani¨ el Paulusma, and Bernard Ries. Dichotomies for maximum matching cut:H-freeness, bounded diameter, bounded radius.Theoretical Com- puter Science, 1017:114795, 2024

work page 2024
[19]

Approximation of knapsack problems with conflict and forcing graphs.J

Ulrich Pferschy and Joachim Schauer. Approximation of knapsack problems with conflict and forcing graphs.J. Comb. Optim., 33(4):1300–1323, May 2017

work page 2017
[20]

On conflict-free cuts: Algorithms and complexity.Information Processing Letters, 187:106503, 2025

Johannes Rauch, Dieter Rautenbach, and U´ everton S Souza. On conflict-free cuts: Algorithms and complexity.Information Processing Letters, 187:106503, 2025

work page 2025