From the 1 of 10 linked papers with an AI index.
10 papers
Hardness of Vertex Splitting: Cographs, Chordal Graphs, and Beyond
Satyabrata Jana, Shivesh K. Roy, R. B. Sandeep
The paper investigates the computational complexity of transforming graphs into cographs, chordal graphs, unit‑interval graphs, and Pₜ‑free graphs via vertex splitting, proving the…
A proof of Seymour's second neighborhood conjecture for oriented graphs with minimum out-degree equal to 7
Arpan Sadhukhan, R. B. Sandeep, Sagnik Sen
We prove Seymour's second neighborhood conjecture on oriented graphs whose minimum out-degree is equal to . This gives, to our knowledge, the first improvement of the minimum ou…
Tight Upper Bounds on Color Reversal by Local Inversions
Hitendra Kumar, Kumud Singh Porte, R. B. Sandeep
A bicoloration of a graph is a map . A local inversion at a vertex complements the subgraph induced by the neighbors of and simultaneously revers…
On the complexity of edge subdivision to -free graphs
Marta Piecyk, R. B. Sandeep
Subdividing an edge in a graph replaces it by a path with one new vertex. For a graph , the \textsc{-free Subdivision} problem asks whether, given a graph an…
Parameterized algorithms for -Inversion
Dhanyamol Antony, L. Sunil Chandran, Dalu Jacob +1
Inversion of a directed graph with respect to a vertex subset is the directed graph obtained from by reversing the direction of every arc whose endpoints both lie in $Y…
Improved upper bounds on color reversal by local inversions
Kumud Singh Porte, RB Sandeep, Kamal Santra
We study the problem of color reversal in bicolored graphs under local inversions. A \emph{bicoloration} of a graph is a mapping . A \emph{local inver…