2017/11/22 by Kamibeppu, Akira
#05C62 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1711.08261
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 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 box(G)≤ χ(G) holds, where χ(G) denotes the chromatic number of G. Bhowmick and Chandran (2010) proved that box(G)≤ χ(G) holds for a graph G with no asteroidal triples. We prove that box(G)≤ χ(G) holds for a graph G in a special family of circulant graphs with an asteroidal triple.