TY - JOUR
T1 - Graph functionality
AU - Alecu, Bogdan
AU - Atminas, Aistis
AU - Lozin, Vadim
N1 - Publisher Copyright:
© 2020 Elsevier Inc.
PY - 2021/3
Y1 - 2021/3
N2 - In the present paper, we introduce the notion of graph functionality, which generalises 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 generalisation 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 is also proper.
AB - In the present paper, we introduce the notion of graph functionality, which generalises 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 generalisation 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 is also proper.
KW - Clique-width
KW - Graph representation
KW - Hereditary class
KW - Permutation graph
UR - http://www.scopus.com/inward/record.url?scp=85096394298&partnerID=8YFLogxK
U2 - 10.1016/j.jctb.2020.11.002
DO - 10.1016/j.jctb.2020.11.002
M3 - Article
AN - SCOPUS:85096394298
SN - 0095-8956
VL - 147
SP - 139
EP - 158
JO - Journal of Combinatorial Theory. Series B
JF - Journal of Combinatorial Theory. Series B
ER -