1. Cubicity, boxicity, and vertex cover
- Author
-
Sunil Chandran, L., Das, Anita, and Shah, Chintan D.
- Subjects
- *
INTERSECTION graph theory , *DIMENSIONS , *CUBES , *SET theory , *INTEGERS , *NUMBER theory , *GRAPH coloring - Abstract
Abstract: A -dimensional box is the cartesian product where each is a closed interval on the real line. The boxicity of a graph , denoted as , is the minimum integer such that is the intersection graph of a collection of -dimensional boxes. A unit cube in -dimensional space or a -cube is defined as the cartesian product where each is a closed interval on the real line of the form . The cubicity of , denoted as , is the minimum such that is the intersection graph of a collection of -cubes. In this paper we show that and , where is the cardinality of a minimum vertex cover of and is the number of vertices of . We also show the tightness of these upper bounds. F.S. Roberts in his pioneering paper on boxicity and cubicity had shown that for a graph , and , where is the number of vertices of , and these bounds are tight. We show that if is a bipartite graph then and this bound is tight. We also show that if is a bipartite graph then . We point out that there exist graphs of very high boxicity but with very low chromatic number. For example there exist bipartite (i.e., 2 colorable) graphs with boxicity equal to . Interestingly, if boxicity is very close to , then chromatic number also has to be very high. In particular, we show that if , , then , where is the chromatic number of . [Copyright &y& Elsevier]
- Published
- 2009
- Full Text
- View/download PDF