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 yJSB inlineImage" height="15" width="47" alt="View the MathML source" style="margin-top: -5px; vertical-align: middle" title="View the MathML source" src="/sd/grey_pxl.gif" data-inlimgeid="1-s2.0-S0012365X15003180-si6.gif"> (respectively yJSB inlineImage" height="15" width="46" alt="View the MathML source" style="margin-top: -5px; vertical-align: middle" title="View the MathML source" src="/sd/grey_pxl.gif" data-inlimgeid="1-s2.0-S0012365X15003180-si7.gif">). It was shown by Adiga and Chandran (2010) that for any graph G$G$, abeaf13bd19bed5f74">yJSB inlineImage" height="16" width="189" alt="View the MathML source" title="View the MathML source" src="/sd/grey_pxl.gif" data-inlimgeid="1-s2.0-S0012365X15003180-si9.gif">, where α(G)$\alpha \left(G\right)$ is the maximum size of an independent set in G$G$. In this note we show that yJSB inlineImage" height="16" width="331" alt="View the MathML source" title="View the MathML source" src="/sd/grey_pxl.gif" data-inlimgeid="1-s2.0-S0012365X15003180-si12.gif">, 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 yJSB inlineImage" height="16" width="229" alt="View the MathML source" title="View the MathML source" src="/sd/grey_pxl.gif" data-inlimgeid="1-s2.0-S0012365X15003180-si14.gif">.

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.