The bounded-expansion characterization via poset dimension
The bounded-expansion characterization via poset dimension
Let be a class of graphs closed under taking subgraphs. For each integer , consider posets of height whose cover graphs belong to .
Bounded-expansion characterization. The class has bounded expansion if and only if, for each , the posets of height whose cover graphs are in have bounded dimension.
The theorem proved in the paper establishes one of the two implications; the converse remains open. Thus the conjecture proposes a characterization of bounded-expansion graph classes in terms of uniformly bounded dimension for bounded-height posets with cover graphs in the class.
Sources & referencesView supporting material
Primary source
Gwenaël Joret, Piotr Micek and Veit Wiechert, “Sparsity and dimension”, arXiv:1507.01120 (2017).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.