The Library
Graph functionality
Tools
Tools
Tools
Alecu, Bogdan, Atminas, Aistis and Lozin, Vadim V. (2021) Graph functionality. Journal of Combinatorial Theory, Series B, 147 . pp. 139-158. doi:10.1016/j.jctb.2020.11.002 ISSN 0095-8956.
|
PDF
WRAP-Graph-functionality-Lozin-2020.pdf - Accepted Version - Requires a PDF viewer. Available under License Creative Commons Attribution Non-commercial No Derivatives 4.0. Download (865Kb) | Preview |
Official URL: http://dx.doi.org/10.1016/j.jctb.2020.11.002
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.
| Item Type: | Journal Article | ||||||||
|---|---|---|---|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software |
||||||||
| Divisions: | Faculty of Science, Engineering and Medicine > Science > Mathematics | ||||||||
| Library of Congress Subject Headings (LCSH): | Computer algorithms, Graph theory, Algorithms, Computer science -- Mathematics, Computer graphics | ||||||||
| Journal or Publication Title: | Journal of Combinatorial Theory, Series B | ||||||||
| Publisher: | Academic Press | ||||||||
| ISSN: | 0095-8956 | ||||||||
| Official Date: | March 2021 | ||||||||
| Dates: |
|
||||||||
| Volume: | 147 | ||||||||
| Page Range: | pp. 139-158 | ||||||||
| DOI: | 10.1016/j.jctb.2020.11.002 | ||||||||
| Status: | Peer Reviewed | ||||||||
| Publication Status: | Published | ||||||||
| Access rights to Published version: | Restricted or Subscription Access | ||||||||
| Description: | Some results presented in this paper appeared in the extended abstract [1] published in the proceedings of the 45th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2019. |
||||||||
| Date of first compliant deposit: | 26 November 2020 | ||||||||
| Date of first compliant Open Access: | 17 November 2021 |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
Downloads
Downloads per month over past year
