@inproceedings{8fae1d04c1454733aafb3153396723a1,

title = "Graph Functionality",

abstract = "In the present paper, we introduce the notion of graph functionality, which generalizes simultaneously several other graph parameters, such as degeneracy or clique-width, in the sense 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. We also prove that bounded functionality implies bounded VC-dimension, i.e. graphs of bounded VC-dimension extend graphs of bounded functionality, and this extension also is proper.",

keywords = "Clique-width, Graph degeneracy, Graph representation, Permutation graph, VC-dimension",

author = "Bogdan Alecu and Aistis Atminas and Vadim Lozin",

note = "Publisher Copyright: {\textcopyright} Springer Nature Switzerland AG 2019.; 45th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2019 ; Conference date: 19-06-2019 Through 21-06-2019",

year = "2019",

doi = "10.1007/978-3-030-30786-8_11",

language = "English",

isbn = "9783030307851",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "135--147",

editor = "Ignasi Sau and Thilikos, {Dimitrios M.}",

booktitle = "Graph-Theoretic Concepts in Computer Science - 45th International Workshop, WG 2019, Revised Papers",

}