Graph functionality

Bogdan Alecu, Aistis Atminas, Vadim Lozin

Research output: Contribution to journalArticlepeer-review

8 Citations (Scopus)

Abstract

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.

Original languageEnglish
Pages (from-to)139-158
Number of pages20
JournalJournal of Combinatorial Theory. Series B
Volume147
DOIs
Publication statusPublished - Mar 2021

Keywords

  • Clique-width
  • Graph representation
  • Hereditary class
  • Permutation graph

Fingerprint

Dive into the research topics of 'Graph functionality'. Together they form a unique fingerprint.

Cite this