13 citations · 48 across the 26 of their papers we have counts for
3 papers · 1 filter
Longest paths in 2-edge-connected cubic graphs
Nikola K. Blanchard, Eldar Fischer, Oded Lachish +1
We prove almost tight bounds on the length of paths in -edge-connected cubic graphs. Concretely, we show that (i) every -edge-connected cubic graph of size has a path of…
Empirical Evaluation of Approximation Algorithms for Generalized Graph Coloring and Uniform Quasi-Wideness
Wojciech Nadara, Marcin Pilipczuk, Roman Rabinovich +2
The notions of bounded expansion and nowhere denseness not only offer robust and general definitions of uniform sparseness of graphs, they also describe the tractability boundary f…
Characterising Bounded Expansion by Neighbourhood Complexity
Felix Reidl, Fernando Sánchez Villaamil, Konstantinos Stavropoulos
We show that a graph class has bounded expansion if and only if it has bounded -neighbourhood complexity, i.e. for any vertex set of any subgraph of $G\in\cal G…