Header menu link for other important links
X
Upper bound on cubicity in terms of boxicity for graphs of low chromatic number
L.S. Chandran, R. Mathew,
Published in Elsevier
2016
Volume: 339
   
Issue: 2
Pages: 443 - 446
Abstract
The boxicity (respectively cubicity) of a graph G is the least integer k such that G can be represented as an intersection graph of axis-parallel k-dimensional boxes (respectively k-dimensional unit cubes) and is denoted by box(G) (respectively cub(G)). It was shown by Adiga and Chandran (2010) that for any graph G, cub(G)?box(G)?log;bsubesub?α(G)?, where α(G) is the maximum size of an independent set in G. In this note we show that cub(G)?2?log;bsubesub(G)?box(G)+χ(G)?log;bsubesub?α(G)?, where χ(G) is the chromatic number of G. This result can provide a much better upper bound than that of Adiga and Chandran for graph classes with bounded chromatic number. For example, for bipartite graphs we obtain cub(G)?2(box(G)+?log;bsubesub?α(G)?). Moreover, we show that for every positive integer k, there exist graphs with chromatic number k such that for every ?>0, the value given by our upper bound is at most (1+?) times their cubicity. Thus, our upper bound is almost tight. ©2015 Published by Elsevier B.V.
About the journal
JournalData powered by TypesetDiscrete Mathematics
PublisherData powered by TypesetElsevier
ISSN0012365X