2014/04/29 by Chandran, L. Sunil, Mathew, Rogers, Rajendraprasad, Deepak
#05C62 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1404.7261
The boxicity (respectively cubicity) of a graph G is the minimum non-negative integer k, such that G can be represented as an intersection graph of axis-parallel k-dimensional boxes (respectively k-dimensional unit cubes) and is denoted by box(G) (respectively cub(G)). It was shown by Adiga and Chandran (Journal of Graph Theory, 65(4), 2010) that for any graph G, cub(G) ≤ box(G) \lceil log2 α \rceil, where α= α(G) is the cardinality of the maximum independent set in G. In this note we show that cub(G) ≤ 2 \lceil log2 χ(G) \rceil box(G) + χ(G) \lceil log2 α(G) \rceil . In general, 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 get, cub(G) ≤ 2 (box(G) + \lceil log2 α(G) \rceil ). Moreover we show that for every positive integer k, there exist graphs with chromatic number k, such that for every ε> 0, the value given by our upper bound is at most (1+ε) times their cubicity. Thus, our upper bound is almost tight.