73 citations · 427 across the 49 of their papers we have counts for
6 papers · 1 filter
Nowhere Dense Graph Classes and Dimension
Gwenaël Joret, Piotr Micek, Patrice Ossona de Mendez +1
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 ov…
Boolean dimension and tree-width
Stefan Felsner, Tamás Mészáros, Piotr Micek
The dimension is a key measure of complexity of partially ordered sets. Small dimension allows succinct encoding. Indeed if has dimension , then to know whether i…
On an extremal problem for poset dimension
Grzegorz Guśpiel, Piotr Micek, Adam Polak
Let be the largest integer such that every poset on elements has a -dimensional subposet on elements. What is the asymptotics of ? It is easy to see that…
A Note on the Minimum Number of Edges in Hypergraphs with Property O
Gal Kronenberg, Christopher Kusch, Ander Lamaison +2
An oriented -uniform hypergraph is said to have Property O if for every linear order of the vertex set, there is some edge oriented consistently with the linear order. Recently…
Burling graphs, chromatic number, and orthogonal tree-decompositions
Stefan Felsner, Gwenaël Joret, Piotr Micek +2
A classic result of Asplund and Grünbaum states that intersection graphs of axis-aligned rectangles in the plane are -bounded. This theorem can be equivalently stated in terms o…
Separating Tree-chromatic number from Path-chromatic Number
Fidel Barrera-Cruz, Stefan Felsner, Tamás Mészáros +4
We apply Ramsey theoretic tools to show that there is a family of graphs which have tree-chromatic number at most~ while the path-chromatic number is unbounded. This resolves a…