{"id":"arxiv/2607.13517","url":"https://arxiv.org/abs/2607.13517","tags":["cs.DS","math.CO"],"score":0,"title":"Hardness of Vertex Splitting: Cographs, Chordal Graphs, and Beyond","domain":"cs.DS","source":"arxiv","authors":["Satyabrata Jana","Shivesh K. Roy","R. B. Sandeep"],"reviews":0,"subject":"cs.DS","summary":"Vertex splitting replaces a vertex (v) by two nonadjacent vertices whose neighborhoods together equal (N(v)). A split is \\emph{exclusive} if these neighborhoods are disjoint and \\emph{shallow} if no newly created vertex is split again. For a graph property (Π), \\textsc{(Π)-Vertex Splitting} asks whether at most (k) splits can transform a graph (G) into one satisfying (Π). We continue the systematic study of this operation and settle several open problems. First, we prove that \\textsc{Cograph Vertex Splitting} is \\textsf{NP}-complete, even on graphs of girth at least 5, resolving a question…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-07-15","reactions":{}}