@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",
}