A sufficient condition for a graph with boxicity at most its chromatic number

Abstract

A box in Euclidean $k$-space is the Cartesian product of $k$ closed intervals on the real line. The boxicity of a graph $G$, denoted by $\text{box}(G)$, is the minimum nonnegative integer $k$ such that $G$ can be isomorphic to the intersection graph of a family of boxes in Euclidean $k$-space. In this paper, we present a sufficient condition for a graph $G$ under which $\text{box}(G)\le \chi (G)$ holds, where $\chi (G)$ denotes the chromatic number of $G$. Bhowmick and Chandran (2010) proved that $\text{box}(G)\le \chi (G)$ holds for a graph $G$ with no asteroidal triples. We prove that $\text{box}(G)\le \chi (G)$ holds for a graph $G$ in a special family of circulant graphs with an asteroidal triple.

10 pages, 4 figures