2008/12/04 by Diptendu Bhowmick, Bhowmick, Diptendu, L. Sunil Chandran +1
Computer Science · Mathematics · #05C62 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Graph theory and applications
paper · pdf · doi:10.48550/arxiv.0812.0894
openalex publication_date 2008/12/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
An axis parallel d-dimensional box is the Cartesian product R1 × R2 × ... × Rd where each Ri is a closed interval on the real line. The \it boxicity of a graph G, denoted as \boxi(G), is the minimum integer d such that G can be represented as the intersection graph of a collection of d-dimensional boxes. An axis parallel unit cube in d-dimensional space or a d-cube is defined as the Cartesian product R1 × R2 × ... × Rd where each Ri is a closed interval on the real line of the form [ai,ai + 1]. The \it cubicity of G, denoted as \cub(G), is the minimum integer d such that G can be represented as the intersection graph of a collection of d-cubes. Let S(m) denote a star graph on m+1 nodes. We define \it claw number of a graph G as the largest positive integer k such that S(k) is an induced subgraph of G and denote it as \claw. Let G be an AT-free graph with chromatic number χ(G) and claw number \claw. In this paper we will show that \boxi(G) ≤ χ(G) and this bound is tight. We also show that \cub(G) ≤ \boxi(G)(\ceillog2 \claw +2) ≤ χ(G)(\ceillog2 \claw +2). If G is an AT-free graph having girth at least 5 then \boxi(G) ≤ 2 and therefore \cub(G) ≤ 2\ceillog2 \claw +4.