5 papers · 1 filter
Awesome graph parameters
Kenny Bešter Štorgel, Clément Dallard, Vadim Lozin +2
For a graph , we denote by the size of a maximum independent set and by the size of a maximum clique in . Our paper lies on the edge of two lines of research,…
Graph Classes Closed under Self-intersection
Konrad K. Dabrowski, Vadim V. Lozin, Martin MilaniÄ +3
A graph class is monotone if it is closed under taking subgraphs. It is known that a monotone class defined by finitely many obstructions has bounded treewidth if and only if one o…
Functionality of Random Graphs
John Sylvester, Viktor Zamaraev, Maksim Zhukovskii
The functionality of a graph is the minimum number such that in every induced subgraph of there exists a vertex whose neighbourhood is uniquely determined by the neighb…
Boolean combinations of graphs
Sarosh Adenwalla, Samuel Braunfeld, John Sylvester +1
Boolean combinations allow combining given combinatorial objects to obtain new, potentially more complicated, objects. In this paper, we initiate a systematic study of this idea ap…
Adjacency Labeling Schemes for Small Classes
Ãdouard Bonnet, Julien Duron, John Sylvester +1
A graph class admits an implicit representation if, for every positive integer , its -vertex graphs have a -bit (adjacency) labeling scheme, i.e., their vertices c…