2020/01/07 by T. Kavaskar, Kavaskar, T.
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2001.01883
openalex publication_date 2020/01/07 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The boxicity of a graph G, denoted by box(G), is the least positive integer ℓ such that G can be isomorphic to the intersection graph of a family of boxes in Euclidean ℓ-space, where box in an Euclidean ℓ-space is the Cartesian product of ℓ closed intervals on the real line. Let k and d be two positive integers with k≥ 2d. The circulant graph Gkd is the graph with vertices set V(Gkd)=\a0, a1,…, ak-1\ and edge set E(Gkd)=\ai aj | d≤ |i-j|≤ k-d\. Denote χ(G) the chromatic number of a graph G. In \citeAki Akira Kamibeppu proved that box(Gkd)≤ χ(Gkd) for some class of circulant graph Gkd and raised the question that the same result holds for all circulant graph. In this short note, we prove that box(Gkd)≤ χ(Gkd), for all k and d with k≥ 2d. This include all circulant graph Gkd. Our proof is very simple and short. This answer the above question.