3 papers
math.CO2018
Boxicity, poset dimension, and excluded minors
Louis Esperet, Veit Wiechert
In this short note, we relate the boxicity of graphs (and the dimension of posets) with their generalized coloring parameters. In particular, together with known estimates, our res…
math.CO2018
Realization of shift graphs as disjointness graphs of 1-intersecting curves in the plane
Torsten Mütze, Bartosz Walczak, Veit Wiechert
It is shown that shift graphs can be realized as disjointness graphs of 1-intersecting curves in the plane. This implies that the latter class of graphs is not -bounded.
cs.DS2015
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…