Boxicity and cubicity of asteroidal triple free graphs

AbstractThe boxicity of a graph G, denoted box(G), is the least integer d such that G is the intersection graph of a family of d-dimensional (axis-parallel) boxes. The cubicity, denoted cub(G), is the least d such that G is the intersection graph of a family of d-dimensional unit cubes. An independent set of three vertices is an asteroidal triple if any two are joined by a path avoiding the neighbourhood of the third. A graph is asteroidal triple free (AT-free) if it has no asteroidal triple. The claw number ψ(G) is the number of edges in the largest star that is an induced subgraph of G.For an AT-free graph G with chromatic number χ(G) and claw number ψ(G), we show that box(G)≤χ(G) and that this bound is sharp. We also show that cub(G)≤box(G)(⌈log2ψ(G)⌉+2)≤χ(G)(⌈log2ψ(G)⌉+2). If G is an AT-free graph having girth at least 5, then box(G)≤2, and therefore cub(G)≤2⌈log2ψ(G)⌉+4