Originators: L.S. Chandran, M.C. Francis, and N. Sivadasan (presented by D.B. West - REGS 2009)
Definitions: The intersection graph of a family of sets is the graph whose vertices correspond to the sets so that vertices are adjacent if and only if the corresponding sets intersect; the family is an intersection representation of the graph. An interval graph is a graph representable as the intersection graph of a family of intervals on the real line. The boxicity of a graph G, written box(G) and introduced by Roberts [R], is the minimum number of interval graphs with vertex set V(G) whose intersection is G.
Background: The traditional definition of box(G) is the minimum d such that G is representable as the intersection graph of a family of d-dimensional axis-parallel boxes. Since two boxes intersect if and only if their projections on the axes intersect, the definitions are equivalent. Boxicity of G can also be expressed as the minimum number of complements of interval graphs whose union is the complement of G.
This latter interpretation has led to many of the upper bounds on box(G) in terms of parameters of the complement of G. For example, box(G) is bounded by the minimum size of a maximal matching in the complement of G (Roberts [R]). When G is dense and its complement is sparse, the boxicity tends to be small. Few good bounds on boxicity when G is sparse are known.
Conjecture 1: (Chandran-Francis-Sivadasan [CFS]) The boxicity function for graphs is bounded by a linear function of the maximum degree.
Comments: The result proved in [CFS] is a quadratic bound in terms of the maximum degree. They show that box(G)≤2Δ(G)² by showing that box(G)≤2χ(G²), where the square of a graph G is the graph obtained from G by adding edges to join nonadjacent vertices that have common neighbors in G. Their method is to use an optimal coloring of G² to define graphs with boxicity 2 whose intersection is G.
Since the boxicity of a disjoint union of graphs equals the maximum of their boxicities, and cycles have boxicity 2, it follows that the boxicity of every graph with maximum degree 2 is at most 2. To understand the problem, one might start by finding the largest boxicity among graphs with maximum degree 3.
Another upper bound on box(G) that uses sparseness of G is tw(G)+2, where tw(G) is the "treewidth" of G [CS]. However, the cartesian product of the path Pn with itself (the n-grid) has treewidth n even though it has maximum degree only 4. Nevertheless, embedding the n-grid in the plane with edges along diagonal lines and replacing the vertices with squares shows that the graph has boxicity 2. What is the boxicity for higher-dimensional grids? Because vertex degrees are additive under cartesian products, the effect of this operation is a natural question when studying Conjecture 1.
Question 2: What is the behavior of boxicity under cartesian product? That is, what is the maximum boxicity of the cartesian product of graphs with boxicities r and s?
References:
[CS] Chandran, L. Sunil; Sivadasan, Naveen; Boxicity and treewidth. J. Combin.
Theory Ser. B 97 (2007), no. 5, 733--744.
[R] Roberts, Fred S. On the boxicity and cubicity of a graph. 1969 Recent
Progress in Combinatorics (Proc. Third Waterloo Conf. on Combinatorics, 1968)
pp. 301--310 Academic Press, New York.
[CFS] Chandran, L. Sunil; Francis, Mathew C.; Sivadasan, Naveen; Boxicity and
maximum degree. J. Combin. Theory Ser. B 98 (2008), no. 2, 443--445.