Alecu, Bogdan, Alekseev, Vladimir E, Atminas, Aistis, Lozin, Vadim and Zamaraev, Viktor 
ORCID: 0000-0001-5755-4141
(2022)
Graph Parameters, Implicit Representations and Factorial Properties.
In: The 33rd International Workshop on Combinatorial Algorithms (IWOCA), 2022-6-7 - 2022-6-9, Trier, Germany.
|
Text
gif-extended-abstract-2021-12-20.pdf - Author Accepted Manuscript Download (315kB) | Preview |
Abstract
A representation of an n-vertex graph G is implicit if it assigns to each vertex of G a binary code of length O(log n) so that the adjacency of two vertices is a function of their codes. A necessary condition for a hereditary class X of graphs to admit an implicit representation is that X has at most factorial speed of growth. This condition, however, is not sufficient, as was recently shown in [10]. Several sufficient conditions for the existence of implicit representations deal with boundedness of some parameters, such as degeneracy or clique-width. In the present paper, we analyse more graph parameters and prove a number of new results related to implicit representation and factorial properties.
| Item Type: | Conference or Workshop Item (Unspecified) |
|---|---|
| Uncontrolled Keywords: | Graph parameter, Hereditary class, Implicit representation, Factorial property |
| Divisions: | Faculty of Science and Engineering > School of Electrical Engineering, Electronics and Computer Science |
| Depositing User: | Symplectic Admin |
| Date Deposited: | 30 Jun 2022 15:28 |
| Last Modified: | 27 Nov 2023 21:05 |
| DOI: | 10.1007/978-3-031-06678-8_5 |
| Related URLs: | |
| URI: | https://livrepository.liverpool.ac.uk/id/eprint/3157506 |
Dimensions
Dimensions
