etd AT Indian Institute of Science >
Division of Electrical Sciences >
Computer Science and Automation (csa) >
Please use this identifier to cite or link to this item:
http://etd.iisc.ernet.in/2005/890

Title:  Boxicity, Cubicity And Vertex Cover 
Authors:  Shah, Chintan D 
Advisors:  Chandran, L Sunil 
Keywords:  Boxicity Cubicity Vortex Cover Graphs  Boxicity Graphs  Cubicity Bipartite Graphs Interval Graphs Intersection Graphs Chromatic Number Box(G) Cub(G) 
Submitted Date:  Aug2008 
Series/Report no.:  G22611 
Abstract:  The boxicity of a graph G, denoted as box(G), is the minimum dimension d for which each vertex of G can be mapped to a ddimensional axisparallel box in Rd such that two boxes intersect if and only if the corresponding vertices of G are adjacent. An axisparallel box is a generalized rectangle with sides parallel to the coordinate axes. If additionally, we restrict all sides of the rectangle to be of unit length, the new parameter so obtained is called the cubicity of the graph G, denoted by cub(G).
F.S. Roberts had shown that for a graph G with n vertices, box(G) ≤ and cub(G) ≤ . A minimum vertex cover of a graph G is a minimum cardinality subset S of the vertex set of G such that each edge of G has at least one endpoint in S. We show that box(G) ≤ +1 and cub(G)≤ t+ ⌈log2(n −t)⌉−1 where t is the cardinality of a minimum vertex cover. Both these bounds are tight.
For a bipartite graph G, we show that box(G) ≤ and this bound is tight. We observe that there exist graphs of very high boxicity but with very low chromatic number. For example, there exist bipartite (2 colorable) graphs with boxicity equal to . Interestingly, if boxicity is very close to , then the chromatic number also has to be very high. In particular, we show that if box(G) = −s, s ≥ 02, then x(G) ≥ where X(G) is the chromatic number of G.
We also discuss some known techniques for ﬁndingan upper boundon the boxicityof a graph representing the graph as the intersection of graphs with boxicity 1 (boxicity 1 graphs are known as interval graphs) and covering the complement of the graph by cointerval graphs (a cointerval graph is the complement of an interval graph). 
URI:  http://etd.iisc.ernet.in/handle/2005/890 
Appears in Collections:  Computer Science and Automation (csa)

Items in etd@IISc are protected by copyright, with all rights reserved, unless otherwise indicated.
