Vaidy Sivaraman

I am an assistant professor in the department of mathematics and statistics at Mississippi State University. (

My main interest is in graph theory: Graph invariants, induced subgraphs, chi-boundedness, graph-matroid symbiosis, signed graphs.

I received my Ph.D. from The Ohio State University in December 2012. My dissertation “Some topics concerning graphs, signed graphs, and matroids” was supervised by Prof. Neil Robertson. (I was his last (22) Ph.D. student.)

Email: or

Research Interests: Graph Theory (structural and algorithmic aspects, induced subgraphs, graph invariants, chi-boundedness), Signed Graphs, Matroid Theory

Particular topics of interest include well-quasi-ordering, graph invariants (particularly chromatic number, Hadwiger number, girth), minor-closed classes of graphs, induced subgraphs, signed graphs, matroids coming from graphs, signed-graphic matroids, and statistical properties of matroids.


1. Two short proofs of the bounded case of S. B. Rao's degree sequence conjecture, Discrete Math. 313 (2013), no. 13, 1500-1501.

2. Bicircular signed-graphic matroids, Discrete Math. 328 (2014), 1–4.

3. A unified proof of Brooks’ theorem and Catlin’s theorem, Discrete Math. 338 (2015) no. 2, 272–273.

4. (with John Maharry, Neil Robertson, and Daniel Slilaty) Flexibility of projective-planar embeddings, J. Combin. Theory Ser. B 122 (2017), 241–300.

5. Some problems on induced subgraphs, Discrete Applied Mathematics, 236 (2018) 422-427.

6. (with Maria Chudnovsky) Odd holes in bull-free graphs, SIAM J. Discrete Math. 32 (2018), no. 2, 951–955.

7. (with Richard Behr, Thomas Zaslavsky) Mock threshold graphs, Discrete Math. 341 (2018) 2159–2178.

8. (with Maria Chudnovsky) Perfect divisibility and 2-divisibility, J. Graph Theory 90 (2019) 54-60.

9. (with Bart Litjens, Sven Polak) Sum-perfect graphs, Discrete Applied Mathematics, 259 (2019) 232-239.

10. An application of the Gyarfas path argument, Discrete Math. 342 (2019) 2306-2307.

11. (with Daniel Slilaty) The graphs that have antivoltages using groups of small order, Discrete Math. 342 (2019) 2951–2965.

12. (with Ringi Kim, O-joung Kwon, Sang-il Oum) Classes of graphs with no long cycle as a vertex-minor are polynomially 𝜒-bounded, J. Combin. Theory Ser. B. 140 (2020) 372-386.

13. (with Katie Cameron, Shenwei Huang, Irena Penev) The class of (P7,C4,C5)-free graphs: decomposition, chi-boundedness, algorithms, J. Graph Theory 93 (2020) 503-552.

14. (with Dan Slilaty) The family of bicircular matroids closed under duality, submitted.

15. (with Stephen Testa) Cop number of 2K_2-free graphs, submitted.

16. Cop number of graphs without long holes, submitted.

17. (with T. Karthick, Jenny Kaufmann) Coloring graph classes with no induced fork via perfect divisibility, submitted.


Current projects include understanding some hereditary classes of graphs, coloring perfect graphs, chi-boundedness, line graphs of directed graphs, antivoltages in graphs, and the ubiquitous Tutte polynomial.

In preparation:

1. (with Bart Litjens, Sven Polak, Bart Sevenster) A characterization of graphs with Dilworth number at most 3.

2. Apexing in hereditary graph classes.

3. (with Thomas Zaslavsky) Smock (special mock threshold) graphs.

4. (with Thomas Zaslavsky) The seven signed Heawood graphs.

5. (with Jan Goedgebeur, Pierre Hauweele) Towards the forbidden induced subgraph characterization for graphs that have a connected dominating set of size 4.

6. The symmetrization operator on hereditary graph classes.

7. Pseudo-line graphs.

8. Some problems on the cop number of a graph.

9. On a relationship between the chromatic number and the number of spanning trees.


1. Neil Robertson

2. John Maharry

3. Daniel Slilaty

4. Maria Chudnovsky

5. Thomas Zaslavsky

6. Richard Behr

7. Bart Litjens

8. Sven Polak

9. Kathie Cameron

10. Shenwei Huang

11. Irena Penev

12. Lex Schrijver

13. Bart Sevenster

14. Stephen Testa

15. Sang-il Oum

16. Ringi Kim,

17. O-joung Kwon

Member of organizing committe:

Member of organizing committee:

Recent talks:

Combinatorics seminar, Binghamton University, Nov 2020

  • Atlanta Lecture Series in Combinatorics and Graph Theory (ALS 25), April 2020, postponed due to pandemic)

  • Workshop on structure and coloring, BIRS, Banff, March 2020 (online)

  • Combinatorics seminar, University of Mississippi, Nov 2019

  • AMS Special session for Tom Zaslavsky, Binghamton, Oct 2019

  • SIAM Discrete math meeting, Vancouver, May 2019

  • Problems on cop number, short presentation in Barbados Graph Theory Workshop, Barbados, March 2019

  • Colloquium, Augusta University, February 2019

  • Colloquium, Mississippi State University, January 2019

  • International Conference on Graph Theory, Lyon, July 2018

  • Combinatorics seminar, University of Amsterdam, June 2018

  • Combinatorics seminar, University of Central Florida, March 2018

  • AMS special session for Neil Robertson, Ohio State, March 2018

Graph theorists working on induced subgraphs

Paul Seymour

Maria Chudnovsky

Alex Scott

Sophie Spirkl

Vasek Chvatal

Kristina Vuskovic

Nicolas Trotignon

Stephan Thomasse

Vadim Lozin

Martin Golumbic

Frederic Maffray (deceased)

Daniel Paulusma

Konrad Dabrowski

Chinh T. Hoang

Kathie Cameron

Shenwei Huang

T. Karthick

Andras Brandstadt

Raffaele Mosca

Dieter Kratsch

Van Bang Le

Ingo Scheiermeyer

Bert Randerath

Martin Milanic