The Library
Cubicity, boxicity, and vertex cover
Tools
Sunil Chandran, L., Das, Anita and Shah, Chintan D. (2009) Cubicity, boxicity, and vertex cover. Discrete Mathematics, Volume 309 (Number 8). pp. 2488-2496. doi:10.1016/j.disc.2008.06.003 ISSN 0012-365X.
PDF
sdarticle11.pdf - Published Version Embargoed item. Restricted access to Repository staff only - Requires a PDF viewer. Download (628Kb) |
Official URL: http://dx.doi.org/10.1016/j.disc.2008.06.003
Abstract
A k-dimensional box is the cartesian product R1×R2×...×Rk where each Ri is a closed interval on the real line. The boxicity of a graph G, denoted as box(G), is the minimum integer k such that G is the intersection graph of a collection of k-dimensional boxes. A unit cube in k-dimensional space or a k-cube is defined as the cartesian product R1×R2×,...×Rk where each Ri is a closed interval on the real line of the form [ai,ai+1]. The cubicity of G, denoted as cub(G), is the minimum k such that G is the intersection graph of a collection of k-cubes. In this paper we show that cub(G)≤t+left ceilinglog(n−t)right ceiling−1 and View the MathML source, where t is the cardinality of a minimum vertex cover of G and n is the number of vertices of G. 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 G, View the MathML source and View the MathML source, where n is the number of vertices of G, and these bounds are tight. We show that if G is a bipartite graph then View the MathML source and this bound is tight. We also show that if G is a bipartite graph then View the MathML source. 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 View the MathML source. Interestingly, if boxicity is very close to View the MathML source, then chromatic number also has to be very high. In particular, we show that if View the MathML source, s≥0, then View the MathML source, where χ(G) is the chromatic number of G.
Item Type: | Journal Article | ||||
---|---|---|---|---|---|
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||
Journal or Publication Title: | Discrete Mathematics | ||||
Publisher: | Elsevier BV | ||||
ISSN: | 0012-365X | ||||
Official Date: | 28 April 2009 | ||||
Dates: |
|
||||
Volume: | Volume 309 | ||||
Number: | Number 8 | ||||
Page Range: | pp. 2488-2496 | ||||
DOI: | 10.1016/j.disc.2008.06.003 | ||||
Status: | Peer Reviewed | ||||
Publication Status: | Published | ||||
Access rights to Published version: | Open Access (Creative Commons) | ||||
Date of first compliant deposit: | 26 December 2015 | ||||
Funder: | DST | ||||
Grant number: | SR/S3/EECE/62=2006 |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |