89 citations · 131 across the 24 of their papers we have counts for
3 papers · 1 filter
Decomposition horizons and a characterization of stable hereditary classes of graphs
Samuel Braunfeld, Jaroslav Nešetřil, Patrice Ossona de Mendez +1
The notions of bounded-size and quasibounded-size decompositions with bounded treedepth base classes are central to the structural theory of graph sparsity introduced by two of the…
Distributed domination on sparse graph classes
Ozan Heydt, Simeon Kublenz, Patrice Ossona de Mendez +2
We show that the dominating set problem admits a constant factor approximation in a constant number of rounds in the LOCAL model of distributed computing on graph classes with boun…
Discrepancy and Sparsity
Mario Grobler, Yiting Jiang, Patrice Ossona de Mendez +2
We study the connections between the notions of combinatorial discrepancy and graph degeneracy. In particular, we prove that the maximum discrepancy over all subgraphs of a gra…