Professor Kristina Vušković

Professor Kristina Vušković


Professor Vušković was awarded a BA in Mathematics and Computer Science from New York University in 1989, and a PhD in Algorithms, Combinatorics and Optimization from Carnegie Mellon University in 1994.

She spent two years as an NSERC Canada International Fellow at University of Waterloo, Department of Combinatorics and Optimization, which was followed by a position at the Department of Mathematics of University of Kentucky.

Since 2000 she is at the School of Computing, University of Leeds, where she is the leader of Algorithms and Complexity Research Group. Professor Vušković was awarded Chair in Algorithms and Combinatorics in 2011.

See the  Algorithms and Complexity research theme page for further information.


  • The Algorithms and Complexity theme leader

Research interests

Kristina's research interests are in graph theory, combinatorial optimisation and algorithms. Kristina's present research involves structural analysis of hereditary graph classes, and exploiting structure for construction of efficient algorithms.

Current research grant:

Structure of Hereditary Graph Classes and Its Algorithmic Consequences (2016-2021)
PI: Prof Kristina Vušković
Funder: EPSRC (EP/N019660/1)

Selected publications:

  • Chudnovsky M, Lo I, Maffray F, Trotignon N, Vušković K Coloring square-free Berge graphs. Submitted to Journal of Combinatorial Theory. Series B.
  • (An article about this paper appeared in Quanta Magazine: Theorists Draw Closer to Perfect Coloring, October 20, 2015
  • Chudnovsky M, Trotignon N, Trunck T, Vušković K Coloring perfect graphs with no balanced skew-partitions. Journal of Combinatorial Theory. Series B, vol. 115, pp.26-65. 2015.
  • da Silva MVG, Vušković K Decomposition of even-hole-free graphs with star cutsets and 2-joins. Journal of Combinatorial Theory. Series B, vol. 103, pp.144-183. 2013.
  • Trotignon N, Vuskovic K Combinatorial optimization with 2-joins. Journal of Combinatorial Theory: Series B, vol. 102, pp.153-185. 2012.
  • Trotignon N, Vuskovic K A Structure Theorem for Graphs with No Cycle with a Unique Chord and Its Consequences. Journal of Graph Theory, vol. 63, pp.31-67. 2010.
  • Kloks T, Muller H, Vuskovic K Even-hole-free graphs that do not contain diamonds: A structure theorem and its consequences. Journal of Combinatorial Theory: Series B, vol. 99, pp.733-800. 2009.
  • Chudnovsky M, Cornuejols G, Liu X, Seymour P, Vuskovic K Recognizing Berge graphs. Combinatorica, vol. 25, pp.143-186. 2005.
  • Conforti M, Cornuejols G, Vuskovic K Square-free perfect graphs. Journal of Combinatorial Theory: Series B, vol. 90, pp.257-307. 2004.
<h4>Research projects</h4> <p>Any research projects I'm currently working on will be listed below. Our list of all <a href="">research projects</a> allows you to view and search the full list of projects in the faculty.</p>


  • BA, Mathematics and Computer Science, New York University, 1989
  • PhD, Algorithms, Combinatorics and Optimization, Carnegie Mellon University, 1994

Student education

  • Introduction to Discrete Mathematics (level 1)
  • Graph Theory: Structure and Algorithms (level 5)

Research groups and institutes

  • Algorithms and Complexity
<h4>Postgraduate research opportunities</h4> <p>We welcome enquiries from motivated and qualified applicants from all around the world who are interested in PhD study. Our <a href="">research opportunities</a> allow you to search for projects and scholarships.</p>