Name
Abstract | ||
|---|---|---|
Nowhere dense graph classes provide one of the least restrictive notions of sparsity for graphs. Several equivalent characterizations of nowhere dense classes have been obtained over the years, using a wide range of combinatorial objects. In this paper we establish a new characterization of nowhere dense classes, in terms of poset dimension: A monotone graph class is nowhere dense if and only if for every h⩾1 and every ε > 0, posets of height at most h with n elements and whose cover graphs are in the class have dimension $$\mathcal{O}(n^\epsilon)$$. |
Year | DOI | Venue |
|---|---|---|
2019 | 10.1007/s00493-019-3892-8 | Combinatorica |
Keywords | Field | DocType |
06A07, 05C35 | Discrete mathematics,Graph,Combinatorics,Nowhere dense set,If and only if,Monotone polygon,Partially ordered set,Mathematics | Journal |
Volume | Issue | ISSN |
39 | 5 | 0209-9683 |
Citations | PageRank | References |
1 | 0.36 | 0 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Gwenaël Joret | 1 | 196 | 28.64 |
| piotr micek | 2 | 153 | 27.33 |
| Patrice Ossona de Mendez | 3 | 675 | 47.97 |
| veit wiechert | 4 | 32 | 6.49 |