Cubicity of Interval Graphs and the Claw Number

Let G(V,E) be a simple, undirected graph. A b-dimensional box is a Cartesian product I1×I2×⋯×Ib, where each Ii is a closed interval on the real line. When each interval has unit length we have a b-dimensional cube. The cubicity (respectively boxicity) of G, cub(G) (box(G)) is the minimum positive integer b such that the vertices in G can be mapped to axis parallel b-dimensional cubes (boxes) in such a way that two vertices are adjacent in G if and only if their assigned cubes (boxes) intersect. Suppose S(m) denotes a star graph on m+1 nodes. We define claw number ψ(G) to be the largest positive integer m such that S(m) is an induced subgraph of G. In this paper we show that for an interval graph G⌈log2ψ(G)⌉⩽cub(G)⩽⌈log2ψ(G)⌉+2. We also show that cub(G)⩽⌈log2α⌉, where α is the independence number of G. From this we have, for any graph G, cub(G)⩽box(G)⌈log2α⌉.