Vaidy Sivaraman

activity

20112026

most citedClasses of graphs with no long cycle as a vertex-minor are polynomially

χ

-bounded

9 citations · 27 across the 19 of their papers we have counts for

collaborators

Showing 2017Show all

4 papers · 1 filter

math.CO2017★ 2 cited

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 $G$ to be sum-perfect if for every induced subgraph $H$ of $G$ , $α (H) + ω (H) \geq ∣ V (H) ∣$ .…

math.CO2017

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…

math.CO2017

Perfect divisibility and 2-divisibility

Maria Chudnovsky, Vaidy Sivaraman

A graph $G$ is said to be $2$ -divisible if for all (nonempty) induced subgraphs $H$ of $G$ , $V (H)$ can be partitioned into two sets $A, B$ such that $ω (A) < ω (H)$ and $ω (B) < ω (H)$ .…

math.CO2017

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…