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 results imply that any graph with no $K_t$-minor can be represented as the intersection of $O(t^2\log t)$ interval graphs (improving the previous bound of $O(t^4)$), and as the intersection of $\tfrac{15}2 t^2$ circular-arc graphs.
@article{10_37236_7787,
author = {Louis Esperet and Veit Wiechert},
title = {Boxicity, poset dimension, and excluded minors},
journal = {The electronic journal of combinatorics},
year = {2018},
volume = {25},
number = {4},
doi = {10.37236/7787},
zbl = {1409.05085},
url = {http://geodesic.mathdoc.fr/articles/10.37236/7787/}
}
TY - JOUR
AU - Louis Esperet
AU - Veit Wiechert
TI - Boxicity, poset dimension, and excluded minors
JO - The electronic journal of combinatorics
PY - 2018
VL - 25
IS - 4
UR - http://geodesic.mathdoc.fr/articles/10.37236/7787/
DO - 10.37236/7787
ID - 10_37236_7787
ER -
%0 Journal Article
%A Louis Esperet
%A Veit Wiechert
%T Boxicity, poset dimension, and excluded minors
%J The electronic journal of combinatorics
%D 2018
%V 25
%N 4
%U http://geodesic.mathdoc.fr/articles/10.37236/7787/
%R 10.37236/7787
%F 10_37236_7787
Louis Esperet; Veit Wiechert. Boxicity, poset dimension, and excluded minors. The electronic journal of combinatorics, Tome 25 (2018) no. 4. doi: 10.37236/7787
