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

详细信息    查看全文

• 作者：L. Sunil Chandran^a ; ^{sunil@csa.iisc.ernet.in" class="auth_mail" title="E-mail the corresponding author} ; Rogers Mathew^b ; ^{rogersmathew@gmail.com" class="auth_mail" title="E-mail the corresponding author} ; Deepak Rajendraprasad^c ; ^{deepakmail@gmail.com" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Boxicity ; Cubicity ; Chromatic number
• 刊名：Discrete Mathematics
• 出版年：2016
• 出版时间：6 February 2016
• 年：2016
• 卷：339
• 期：2
• 页码：443-446
• 全文大小：353 K

文摘

The boxicity (respectively cubicity  ) of a graph G$G$ is the least integer k$k$ such that G$G$ can be represented as an intersection graph of axis-parallel k$k$-dimensional boxes (respectively k$k$-dimensional unit cubes) and is denoted by $\mathrm{box}\left(G\right)$ (respectively $\mathrm{cub}\left(G\right)$). It was shown by Adiga and Chandran (2010) that for any graph G$G$, $\mathrm{cub}\left(G\right)\le \mathrm{box}\left(G\right)\lceil {log}_2\alpha \left(G\right)\rceil$, where α(G)$\alpha \left(G\right)$ is the maximum size of an independent set in G$G$. In this note we show that $\mathrm{cub}\left(G\right)\le 2\lceil {log}_2\chi \left(G\right)\rceil \mathrm{box}\left(G\right)+\chi \left(G\right)\lceil {log}_2\alpha \left(G\right)\rceil$, where χ(G)$\chi \left(G\right)$ 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 $\mathrm{cub}\left(G\right)\le 2(\mathrm{box}\left(G\right)+\lceil {log}_2\alpha \left(G\right)\rceil )$.

Moreover, we show that for every positive integer k$k$, there exist graphs with chromatic number k$k$ 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.