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

Akira Kamibeppu

Published 2017-11-22Version 1

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 of a graph under which $\text{box}(G)\leq \chi (G)$ holds, where $\chi (G)$ denotes the chromatic number of $G$. Bhowmick and Chandran (2010) proved that $\text{box}(G)\leq \chi (G)$ holds for an asteroidal triple free graph. We give an example of a family of graphs with an asteroidal triple each of which satisfies $\text{box}(G)\leq \chi (G)$. This also contributes the conjecture $\text{box}(G)=O(\Delta_G)$ mentioned by Chandran et al. (2008) from the viewpoint of making the graphs clear, where $\Delta_G$ is the maximum degree of a graph $G$.