Upper bound on cubicity in terms of boxicity for graphs of low chromatic number

The boxicity (respectively cubicity  ) of a graph GG is the least integer kk such that GG can be represented as an intersection graph of axis-parallel kk-dimensional boxes (respectively kk-dimensional unit cubes) and is denoted by box(G) (respectively cub(G)). It was shown by Adiga and Chandran (2010) that for any graph GG, cub(G)≤box(G)⌈log2α(G)⌉, where α(G)α(G) is the maximum size of an independent set in GG. In this note we show that cub(G)≤2⌈log2χ(G)⌉box(G)+χ(G)⌈log2α(G)⌉, where χ(G)χ(G) is the chromatic number of G. This result can provide a much better upper bound than that of Adiga and Chandran for graph classes with bounded chromatic number. For example, for bipartite graphs we obtain cub(G)≤2(box(G)+⌈log2α(G)⌉).Moreover, we show that for every positive integer kk, there exist graphs with chromatic number kk such that for every ϵ>0ϵ>0, the value given by our upper bound is at most (1+ϵ)(1+ϵ) times their cubicity. Thus, our upper bound is almost tight.