Graduate Seminars

back Back to all Graduate Seminars

CS Graduate Seminar: Graph functionality

Start Date: September 17, 2018
End Date: September 17, 2018

By Professor Vadim Lozin (University of Warwick, UK)

In this talk, we introduce a new graph parameter under the name functionality. We show that functionality generalizes simultaneously several other graph parameters, such as degeneracy or clique-width, by proving that bounded degeneracy or bounded clique-width imply bounded functionality. Moreover, we show that this generalization is proper by revealing classes of graphs of unbounded degeneracy and clique-width, where functionality is bounded by a constant. This includes permutation graphs and unit interval graphs. We also observe that bounded functionality implies bounded VC-dimension, i.e. graphs of bounded VC-dimension extend graphs of bounded functionality, and this extension is also proper. Joint work with B. Alecu.

Biography: Vadim Lozin is a Professor of Mathematics at the University of Warwick (UK). In the past, he also has held academic and visiting positions in the USA, Russia, Sweden, Switzerland, Portugal, Germany, Canada, Saudi Arabia, Brazil and France. He is the Managing Editor of "Electronic Notes in Discrete Mathematics" (Elsevier), an Associate Editor of "Discrete Applied Mathematics" (Elsevier) and a member of the editorial board of "Discussiones Mathematicae Graph Theory" (De Gruyter). He is an author of 3 books and over 100 journal publications in the area of graph theory, combinatorics, and discrete mathematics. Eight Ph.D. dissertations have been defended under the supervision of Professor Lozin.

More Information:

For more info contact: Professor Mikhail Moshkov: email:
Date: Monday 17th Sep 2018
Time:12:00 PM - 01:00 PM
Location: Building 9 - Hall 1
Refreshments: Light Lunch will presented at 11:45