Cubicity, boxicity, and vertex cover

A kk-dimensional box is the cartesian product R1×R2×⋯×RkR1×R2×⋯×Rk where each RiRi is a closed interval on the real line. The boxicity   of a graph GG, denoted as box(G)box(G), is the minimum integer kk such that GG is the intersection graph of a collection of kk-dimensional boxes. A unit cube in kk-dimensional space or a kk-cube is defined as the cartesian product R1×R2×⋯×RkR1×R2×⋯×Rk where each RiRi is a closed interval on the real line of the form [ai,ai+1][ai,ai+1]. The cubicity   of GG, denoted as cub(G)cub(G), is the minimum kk such that GG is the intersection graph of a collection of kk-cubes. In this paper we show that cub(G)≤t+⌈log(n−t)⌉−1cub(G)≤t+⌈log(n−t)⌉−1 and box(G)≤⌊t2⌋+1, where tt is the cardinality of a minimum vertex cover of GG and nn is the number of vertices of GG. We also show the tightness of these upper bounds.F.S. Roberts in his pioneering paper on boxicity and cubicity had shown that for a graph GG, box(G)≤⌊n2⌋ and cub(G)≤⌈2n3⌉, where nn is the number of vertices of GG, and these bounds are tight. We show that if GG is a bipartite graph then box(G)≤⌈n4⌉ and this bound is tight. We also show that if GG is a bipartite graph then cub(G)≤n2+⌈logn⌉−1. We point out that there exist graphs of very high boxicity but with very low chromatic number. For example there exist bipartite (i.e., 2 colorable) graphs with boxicity equal to n4. Interestingly, if boxicity is very close to n2, then chromatic number also has to be very high. In particular, we show that if box(G)=n2−s, s≥0s≥0, then χ(G)≥n2s+2, where χ(G)χ(G) is the chromatic number of GG.