8 papers
Set-defined graph classes: -boundedness meets tropical algebra
Sarosh Adenwalla, Samuel Braunfeld, Tomáš Hons +2
We study set-defined graph classes: hereditary classes whose vertices are assigned fixed-length numerical tuples, with adjacency determined solely by equality patterns among coordi…
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…
Randomized Communication and Implicit Graph Representations
Nathaniel Harms, Sebastian Wild, Viktor Zamaraev
We initiate the focused study of constant-cost randomized communication, with emphasis on its connection to graph representations. We observe that constant-cost randomized communic…
Temporal Exploration of Random Spanning Tree Models
Samuel Baguley, Andreas Göbel, Nicolas Klodt +3
The Temporal Graph Exploration problem (TEXP) takes as input a temporal graph, i.e., a sequence of graphs on the same vertex set, and asks for a walk of s…
Complexity of learning matchings and half graphs via edge queries
Nikhil S. Mande, Swagato Sanyal, Viktor Zamaraev
The problem of learning or reconstructing an unknown graph from a known family via partial-information queries arises as a mathematical model in various contexts. The most basic ty…