Implicit representations and factorial properties of graphs

DOI10.1016/J.DISC.2014.09.008MaRDI QIDQ472962zbMATH OpenOpenAlexFDO

Authors Vadim Lozin, Victor Zamaraev, Aistis Atminas, Andrew Collins

Publication date 20 November 2014

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1410.4084

zbMATH Keywords

factorial propertyhereditary classimplicit representation

Mathematics Subject Classification ID

Graph representations (geometric and intersection representations, etc.) (05C62)

Abstract: The idea of implicit representation of graphs was introduced in [S. Kannan, M. Naor, S. Rudich, Implicit representation of graphs, SIAM J. Discrete Mathematics, 5 (1992) 596--603] and can be defined as follows. A representation of an $n$-vertex graph $G$ is said to be implicit if it assigns to each vertex of $G$ a binary code of length $O(logn)$ so that the adjacency of two vertices is a function of their codes. Since an implicit representation of an $n$-vertex graph uses $O(nlogn)$ bits, any class of graphs admitting such a representation contains $2^{O(nlogn)}$ labelled graphs with $n$ vertices. In the terminology of [J. Balogh, B. Bollob'{a}s, D. Weinreich, The speed of hereditary properties of graphs, J. Combin. Theory B 79 (2000) 131--156] such classes have at most factorial speed of growth. In this terminology, the implicit graph conjecture can be stated as follows: every class with at most factorial speed of growth which is hereditary admits an implicit representation. The question of deciding whether a given hereditary class has at most factorial speed of growth is far from being trivial. In the present paper, we introduce a number of tools simplifying this question. Some of them can be used to obtain a stronger conclusion on the existence of an implicit representation. We apply our tools to reveal new hereditary classes with the factorial speed of growth. For many of them we show the existence of an implicit representation.

Recommendations

• Graph parameters, implicit representations and factorial properties
• scientific article; zbMATH DE number 6851856
• Implicit representation conjecture for semi-algebraic graphs
• Implicat Representation of Graphs
• Shorter Implicit Representation for Planar Graphs and Bounded Treewidth Graphs

Cites work

• A note on the speed of hereditary graph properties
• Boundary properties of factorial classes of graphs
• Clique-width and the speed of hereditary properties
• Efficient graph representations
• Forbidden induced bipartite graphs
• scientific article; zbMATH DE number 1099508 (Why is no real title available?)
• Implicat Representation of Graphs
• Induced subdivisions in \(K_{s,s}\)-free graphs of large average degree
• Locally bounded coverings and factorial properties of graphs
• Nonredundant 1’s in \Gamma -Free Matrices
• On factorial properties of chordal bipartite graphs
• On the size of hereditary classes of graphs
• Proper minor-closed families are small
• The speed of hereditary properties of graphs

Cited in

(18)

• Implicit representation conjecture for semi-algebraic graphs
• Graph parameters, implicit representations and factorial properties
• Classes of graphs without star forests and related graphs
• Shorter Implicit Representation for Planar Graphs and Bounded Treewidth Graphs
• Implicat Representation of Graphs
• scientific article; zbMATH DE number 6851856 (Why is no real title available?)
• Implicit Component-Graph: A Discussion
• Combinatorics and algorithms for quasi-chain graphs
• Graph functionality
• Combinatorics and algorithms for quasi-chain graphs
• Functionality of box intersection graphs
• Graph parameters, implicit representations and factorial properties
• Implicit representation of relations
• Implicit representation of sparse hereditary families
• Graph problems and monotone classes
• Randomized communication and implicit graph representations
• Symmetric-difference (degeneracy) and signed tree models
• On forbidden induced subgraphs for unit disk graphs

This page was built for publication: Implicit representations and factorial properties of graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q472962)