Abstract
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.
More details on graph functionality can be found in the manuscript: https://arxiv.org/abs/1807.01749
Brief 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.