9 citations · 27 across the 19 of their papers we have counts for
24 papers · 1 filter
Structural Bounds and Forbidden Induced Subgraphs for Edge-Add Graph Classes
Jagdeep Singh, Vaidy Sivaraman
A class of graphs is hereditary if it is closed under taking induced subgraphs. We investigate the edge-add class, , consisting of graphs…
Edge-apexing in hereditary classes of graphs
Jagdeep Singh, Vaidy Sivaraman
A class of graphs is called hereditary if it is closed under taking induced subgraphs. We denote by the class of graphs that are at most one edge away from…
Extensions and Deletions of matroid classes closed under flats
Jagdeep Singh, Vaidy Sivaraman
We call a class of matroids hereditary if it is closed under restriction to flats. For a hereditary class , its extension class consists of all matroids in $\mathcal{M…
Hereditary Nordhaus-Gaddum Graphs
Vaidy Sivaraman, Rebecca Whitman
Nordhaus and Gaddum proved in 1956 that the sum of the chromatic number of a graph and its complement is at most . The Nordhaus-Gaddum graphs are the class of graphs…
Apex Graphs and Cographs
Jagdeep Singh, Vaidy Sivaraman, Thomas Zaslavsky
A class of graphs is called hereditary if it is closed under taking induced subgraphs. We denote by the class of graphs that contain a…
Two Hamiltonian cycles
Vaidy Sivaraman, Thomas Zaslavsky
If the line graph of a graph decomposes into Hamiltonian cycles, what is ? We answer this question for decomposition into two cycles.
Coloring graph classes with no induced fork via perfect divisibility
T. Karthick, Jenny Kaufmann, Vaidy Sivaraman
For a graph , will denote its chromatic number, and its clique number. A graph is said to be perfectly divisible if for all induced subgraphs of , $V(H)…
The family of bicircular matroids closed under duality
Vaidy Sivaraman, Daniel Slilaty
We characterize the 3-connected members of the intersection of the class of bicircular and cobicircular matroids. Aside from some exceptional matroids with rank and corank at most…
Cop number of graphs without long holes
Vaidy Sivaraman
A hole in a graph is an induced cycle of length at least 4. We give a simple winning strategy for t-3 cops to capture a robber in the game of cops and robbers played in a graph tha…
Cop number of -free graphs
Vaidy Sivaraman, Stephen Testa
We prove that the cop number of a -free graph is at most if it has diameter or does not have an induced cycle of length , where . We conjecture…
An application of the Gyárfás path argument
Vaidy Sivaraman
We adapt the Gyárfás path argument to prove that cops can capture a robber, in at most moves, in the game of cops and robbers played in a graph that does not contain th…
Classes of graphs with no long cycle as a vertex-minor are polynomially -bounded
Ringi Kim, O-joung Kwon, Sang-il Oum +1
A class of graphs is -bounded if there is a function such that for every graph and every induced subgraph of , . In ad…
The class of -free graphs: decomposition, algorithms, and -boundedness
Kathie Cameron, Shenwei Huang, Irena Penev +1
As usual, () denotes the path on vertices, and () denotes the cycle on vertices. For a family of graphs, we say that a graph $…
Sum-perfect graphs
Bart Litjens, Sven Polak, Vaidy Sivaraman
Inspired by a famous characterization of perfect graphs due to Lovász, we define a graph to be sum-perfect if for every induced subgraph of , .…
Four NP-complete problems about generalizations of perfect graphs
Vaidy Sivaraman
We show that the following problems are NP-complete. 1. Can the vertex set of a graph be partitioned into two sets such that each set induces a perfect graph? 2. Is the difference…
Perfect divisibility and 2-divisibility
Maria Chudnovsky, Vaidy Sivaraman
A graph is said to be -divisible if for all (nonempty) induced subgraphs of , can be partitioned into two sets such that and .…
Odd holes in bull-free graphs
Maria Chudnovsky, Vaidy Sivaraman
The complexity of testing whether a graph contains an induced odd cycle of length at least five is currently unknown. In this paper we show that this can be done in polynomial time…
Some problems on induced subgraphs
Vaidy Sivaraman
We discuss some problems related to induced subgraphs. The first problem is about getting a good upper bound for the chromatic number in terms of the clique number for graphs in wh…
Mock Threshold Graphs
Richard Behr, Vaidy Sivaraman, Thomas Zaslavsky
Mock threshold graphs are a simple generalization of threshold graphs that, like threshold graphs, are perfect graphs. Our main theorem is a characterization of mock threshold grap…
Frustration in signed graphs
Vaidy Sivaraman
Zaslavsky conjectured the following: The minimum number of vertices to be deleted to restore balance in a subcubic signed graph is the same as the minimum number of edges to be del…
A unified proof of Brooks' theorem and Catlin's theorem
Vaidy Sivaraman
We give a new proof of Brooks' theorem that immediately implies a strengthening of Brooks' theorem, known as Catlin's theorem.
Bicircular signed-graphic matroids
Vaidy Sivaraman
Several matroids can be defined on the edge set of a graph. Although historically the cycle matroid has been the most studied, in recent times, the bicircular matroid has cropped u…
Labelled version of the almost bounded case of S. B. Rao's degree sequence conjecture
Vaidy Sivaraman
S. B. Rao conjectured that graphic sequences are well-quasi-ordered under an inclusion based on induced subgraphs. This conjecture has now been proved by Chudnovsky and Seymour. We…
Two short proofs of the bounded case of S.B. Rao's degree sequence conjecture
Vaidy Sivaraman
S. B. Rao conjectured that graphic sequences are well-quasi-ordered under an inclusion based on induced subgraphs. This conjecture has now been settled completely by M. Chudnovsky…