12 citations · 32 across the 8 of their papers we have counts for
4 papers · 1 filter
Grid Intersection Graphs and Order Dimension
Steven Chaplick, Stefan Felsner, Udo Hoffmann +1
We study subclasses of grid intersection graphs from the perspective of order dimension. We show that partial orders of height two whose comparability graph is a grid intersection…
Sparsity and dimension
Gwenaël Joret, Piotr Micek, Veit Wiechert
We prove that posets of bounded height whose cover graphs belong to a fixed class with bounded expansion have bounded dimension. Bounded expansion, introduced by Nešetřil and Osson…
Topological minors of cover graphs and dimension
Piotr Micek, Veit Wiechert
We show that posets of bounded height whose cover graphs exclude a fixed graph as a topological minor have bounded dimension. This result was already proven by Walczak. However, ou…
An on-line competitive algorithm for coloring bipartite graphs without long induced paths
Piotr Micek, Veit Wiechert
The existence of an on-line competitive algorithm for coloring bipartite graphs remains a tantalizing open problem. So far there are only partial positive results for bipartite gra…