Graph functionality

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.