Answers are grounded in this paper and cite their sources.
This research demonstrates NP-completeness of claw-free exclusive vertex splitting, indicating polynomial-time solvability for graphs of maximum degree 4.
Vertex splitting consists of taking a vertex v in a graph and replacing it with two non-adjacent vertices whose combined neighborhoods is the neighborhood of v. The split is said to be exclusive when these neighborhoods are disjoint. In the Claw-Free (Exclusive) Vertex Splitting problem, we are given a graph G and an integer k, and we are asked if we can perform at most k (exclusive) vertex splits to obtain a claw-free graph. We consider the complexity of Claw-Free Exclusive Vertex Splitting and prove it to be NP-complete in general, while admitting a polynomial-time algorithm when the input graph has maximum degree 4. This result settles an open problem posed in [Firbas & Sorge, ISAAC 2024]. We also show that our results can be generalized to K1,c-Free Vertex Splitting for all c ≥ 3.
No takes yet. Share an insight, caveat, or question.
Abu-Khzam et al. (2025) studied this question.
Synapse has enriched 8 closely related papers on similar clinical questions. Consider them for comparative context: