Boxicity and Cubicity of Asteroidal Triple free graphs

Abstract

An axis parallel $d$-dimensional box is the Cartesian product $R_1\times R_2\times ...\times R_d$ where each $R_i$ is a closed interval on the real line. The {\it boxicity} of a graph $G$, denoted as $\boxi(G)$, is the minimum integer $d$ such that $G$ can be represented as the intersection graph of a collection of $d$-dimensional boxes. An axis parallel unit cube in $d$-dimensional space or a $d$-cube is defined as the Cartesian product $R_1\times R_2\times ...\times R_d$ where each $R_i$ is a closed interval on the real line of the form $[a_i,a_i+1]$. The {\it cubicity} of $G$, denoted as $\cub(G)$, is the minimum integer $d$ such that $G$ can be represented as the intersection graph of a collection of $d$-cubes. Let $S(m)$ denote a star graph on $m+1$ nodes. We define {\it claw number} of a graph $G$ as the largest positive integer $k$ such that $S(k)$ is an induced subgraph of $G$ and denote it as $\claw$. Let $G$ be an AT-free graph with chromatic number $\chi (G)$ and claw number $\claw$. In this paper we will show that $\boxi(G) \leq χ(G)$ and this bound is tight. We also show that $\cub(G) \leq \boxi(G)(\ceil{\log_2 \claw} +2)$ $\le$ $χ(G)(\ceil{\log_2 \claw} +2)$. If $G$ is an AT-free graph having girth at least 5 then $\boxi(G) \leq 2$ and therefore $\cub(G) \leq 2\ceil{\log_2 \claw} +4$.

15 pages: We are replacing our earlier paper regarding boxicity of permutation graphs with a superior result. Here we consider the boxicity of AT-free graphs, which is a super class of permutation graphs