9 citations · 21 across the 18 of their papers we have counts for
13 papers · 1 filter
Tree-independence number of -free graphs with no large bicliques
Václav Blažej, J. Pascal Gollin, Tomáš Hons +5
The tree-independence number of a graph is the minimum, over all tree-decompositions of the graph, of the maximum size of an independent set contained in a bag. Graph classes of bo…
Faithful universal graphs for minor-closed classes
Paul Bastide, Louis Esperet, Carla Groenland +3
It was proved by Huynh, Mohar, Šámal, Thomassen and Wood in 2021 that any countable graph containing every countable planar graph as a subgraph has an infinite clique minor. We pro…
Subgraph-universal planar graphs for trees
Helena Bergold, Vesna Iršič, Robert Lauff +3
We show that there exists an outerplanar graph on vertices for that contains every tree on vertices as a subgraph. This exten…
On the local resilience of random geometric graphs with respect to connectivity and long cycles
Alberto Espuny Díaz, Lyuben Lichev, Alexandra Wesolek
Given an increasing graph property , a graph is -resilient with respect to if, for every spanning subgraph where each vertex keeps…
Cops and Robber on Hyperbolic Manifolds
Vesna Iršič, Bojan Mohar, Alexandra Wesolek
The Cops and Robber game on geodesic spaces is a pursuit-evasion game with discrete steps which captures the behavior of the game played on graphs, as well as that of continuous pu…
A Note on the 2-Colored Rectilinear Crossing Number of Random Point Sets in the Unit Square
Sergio Cabello, Éva Czabarka, Ruy Fabila-Monroy +5
Let be a set of four points chosen independently, uniformly at random from a square. Join every pair of points of with a straight line segment. Color these edges red if the…
Sharp threshold for embedding balanced spanning trees in random geometric graphs
Alberto Espuny Díaz, Lyuben Lichev, Dieter Mitsche +1
A rooted tree is balanced if the degree of a vertex depends only on its distance to the root. In this paper we determine the sharp threshold for the appearance of a large family of…
A note on highly connected -minor free graphs
Nicolas Bousquet, Théo Pierron, Alexandra Wesolek
We show that every -connected -minor free graph with minimum degree at least has maximum degree at most . As a consequence, we show that every 3-connected…
Every graph is eventually Turán-good
Natasha Morrison, JD Nir, Sergey Norin +2
Let be a graph. We show that if is large enough as a function of , then the -partite Turán graph maximizes the number of copies of among all -free graphs…
Sparse graphs with bounded induced cycle packing number have logarithmic treewidth
Marthe Bonamy, Édouard Bonnet, Hugues Déprés +5
A graph is -free if it does not contain pairwise vertex-disjoint and non-adjacent cycles. We prove that "sparse" (here, not containing large complete bipartite g…
On Asymptotic Packing of Geometric Graphs
Daniel W. Cranston, Jiaxi Nie, Jacques Verstraëte +1
A set of geometric graphs is {\em geometric-packable} if it can be asymptotically packed into every sequence of drawings of the complete graph . For example, the set of geomet…
A note on connected greedy edge colouring
Marthe Bonamy, Carla Groenland, Carole Muller +3
Following a given ordering of the edges of a graph , the greedy edge colouring procedure assigns to each edge the smallest available colour. The minimum number of colours thus i…
Bootstrap percolation in Ore-type graphs
Alexandra Wesolek
The -neighbour bootstrap process describes an infection process on a graph, where we start with a set of initially infected vertices and an uninfected vertex becomes infected as…