Boxicity of Circulant Graph $G_k^d$

Abstract

The boxicity of a graph $G$, denoted by $box(G)$, is the least positive integer $\ell$ such that $G$ can be isomorphic to the intersection graph of a family of boxes in Euclidean $\ell$-space, where box in an Euclidean $\ell$-space is the Cartesian product of $\ell$ closed intervals on the real line. Let $k$ and $d$ be two positive integers with $k\ge 2d$. The circulant graph $G_k^d$ is the graph with vertices set $V(G_k^d)=\{a_0,a_1,\dots ,a_{k-1}\}$ and edge set $E(G_k^d)=\{a_i{a}_j|d\le |i-j|\le k-d\}$. Denote $\chi (G)$ the chromatic number of a graph $G$. In \cite{Aki} Akira Kamibeppu proved that $box(G_k^d)\le \chi (G_k^d)$ for some class of circulant graph $G_k^d$ and raised the question that the same result holds for all circulant graph. In this short note, we prove that $box(G_k^d)\le \chi (G_k^d)$, for all $k$ and $d$ with $k\ge 2d$. This include all circulant graph $G_k^d$. Our proof is very simple and short. This answer the above question.

Improve the paper