Upper bound on cubicity in terms of boxicity for graphs of low chromatic number

preprint2014arXivOpen access

Abstract

The boxicity (respectively cubicity) of a graph GG is the minimum non-negative integer kk, such that GG can be represented as an intersection graph of axis-parallel kk-dimensional boxes (respectively kk-dimensional unit cubes) and is denoted by box(G)box(G) (respectively cub(G)cub(G)). It was shown by Adiga and Chandran (Journal of Graph Theory, 65(4), 2010) that for any graph GG, cub(G)≤cub(G) \le box(G)⌈log⁡2α⌉(G) \left \lceil \log_2 α\right \rceil, where α=α(G)α= α(G) is the cardinality of the maximum independent set in GG. In this note we show that cub(G)≤2⌈log⁡2χ(G)⌉box(G)+χ(G)⌈log⁡2α(G)⌉cub(G) \le 2 \left \lceil \log_2 χ(G) \right \rceil box(G) + χ(G) \left \lceil \log_2 α(G) \right \rceil . In general, 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 get, cub(G)≤2(box(G)+⌈log⁡2α(G)⌉)cub(G) \le 2 (box(G) + \left \lceil \log_2 α(G) \right \rceil ). Moreover we show that for every positive integer kk, there exist graphs with chromatic number kk, such that for every ε>0ε> 0, the value given by our upper bound is at most (1+ε)(1+ε) times their cubicity. Thus, our upper bound is almost tight.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.