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 hmlsrc">hImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15003180&_mathId=si1.gif&_user=111111111&_pii=S0012365X15003180&_rdoc=1&_issn=0012365X&md5=3de87e17adfef834326e23d24e723a6a" title="Click to view the MathML source">GhContainer hidden">hCode">h altimg="si1.gif" overflow="scroll">Gh> is the least integer hmlsrc">hImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15003180&_mathId=si2.gif&_user=111111111&_pii=S0012365X15003180&_rdoc=1&_issn=0012365X&md5=1e5dec6f77b9e911c424ea10d625e268" title="Click to view the MathML source">khContainer hidden">hCode">h altimg="si2.gif" overflow="scroll">kh> such that hmlsrc">hImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15003180&_mathId=si1.gif&_user=111111111&_pii=S0012365X15003180&_rdoc=1&_issn=0012365X&md5=3de87e17adfef834326e23d24e723a6a" title="Click to view the MathML source">GhContainer hidden">hCode">h altimg="si1.gif" overflow="scroll">Gh> can be represented as an intersection graph of axis-parallel hmlsrc">hImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15003180&_mathId=si2.gif&_user=111111111&_pii=S0012365X15003180&_rdoc=1&_issn=0012365X&md5=1e5dec6f77b9e911c424ea10d625e268" title="Click to view the MathML source">khContainer hidden">hCode">h altimg="si2.gif" overflow="scroll">kh>-dimensional boxes (respectively hmlsrc">hImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15003180&_mathId=si2.gif&_user=111111111&_pii=S0012365X15003180&_rdoc=1&_issn=0012365X&md5=1e5dec6f77b9e911c424ea10d625e268" title="Click to view the MathML source">khContainer hidden">hCode">h altimg="si2.gif" overflow="scroll">kh>-dimensional unit cubes) and is denoted by hmlsrc">he MathML source" class="mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15003180&_mathId=si6.gif&_user=111111111&_pii=S0012365X15003180&_rdoc=1&_issn=0012365X&md5=b898b74dd9ea347f25b317c99b9f1791">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">hContainer hidden">hCode">h altimg="si6.gif" overflow="scroll">hvariant="normal">box(G)h> (respectively hmlsrc">he MathML source" class="mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15003180&_mathId=si7.gif&_user=111111111&_pii=S0012365X15003180&_rdoc=1&_issn=0012365X&md5=68595d4e733e974741e3c0306296c130">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">hContainer hidden">hCode">h altimg="si7.gif" overflow="scroll">hvariant="normal">cub(G)h>). It was shown by Adiga and Chandran (2010) that for any graph hmlsrc">hImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15003180&_mathId=si1.gif&_user=111111111&_pii=S0012365X15003180&_rdoc=1&_issn=0012365X&md5=3de87e17adfef834326e23d24e723a6a" title="Click to view the MathML source">GhContainer hidden">hCode">h altimg="si1.gif" overflow="scroll">Gh>, hmlsrc">he MathML source" class="mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15003180&_mathId=si9.gif&_user=111111111&_pii=S0012365X15003180&_rdoc=1&_issn=0012365X&md5=385cf9d453025eabeaf13bd19bed5f74">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">hContainer hidden">hCode">h altimg="si9.gif" overflow="scroll">hvariant="normal">cub(G)≤hvariant="normal">box(G)⌈log2α(G)⌉h>, where hmlsrc">hImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15003180&_mathId=si10.gif&_user=111111111&_pii=S0012365X15003180&_rdoc=1&_issn=0012365X&md5=99688c30f45e5b0baec627ebeac58e85" title="Click to view the MathML source">α(G)hContainer hidden">hCode">h altimg="si10.gif" overflow="scroll">α(G)h> is the maximum size of an independent set in hmlsrc">hImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15003180&_mathId=si1.gif&_user=111111111&_pii=S0012365X15003180&_rdoc=1&_issn=0012365X&md5=3de87e17adfef834326e23d24e723a6a" title="Click to view the MathML source">GhContainer hidden">hCode">h altimg="si1.gif" overflow="scroll">Gh>. In this note we show that hmlsrc">he MathML source" class="mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15003180&_mathId=si12.gif&_user=111111111&_pii=S0012365X15003180&_rdoc=1&_issn=0012365X&md5=517877fafcb8be36a19ba9f3dad3ae30">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">hContainer hidden">hCode">h altimg="si12.gif" overflow="scroll">hvariant="normal">cub(G)≤2⌈log2χ(G)⌉hvariant="normal">box(G)+χ(G)⌈log2α(G)⌉h>, where hmlsrc">hImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15003180&_mathId=si13.gif&_user=111111111&_pii=S0012365X15003180&_rdoc=1&_issn=0012365X&md5=06a4d25b1a55532bf23124c67812bf6e" title="Click to view the MathML source">χ(G)hContainer hidden">hCode">h altimg="si13.gif" overflow="scroll">χ(G)h> 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 hmlsrc">he MathML source" class="mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15003180&_mathId=si14.gif&_user=111111111&_pii=S0012365X15003180&_rdoc=1&_issn=0012365X&md5=0d90bdbaa49daf047b05ccc016c9c1e0">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">hContainer hidden">hCode">h altimg="si14.gif" overflow="scroll">hvariant="normal">cub(G)≤2(hvariant="normal">box(G)+⌈log2α(G)⌉)h>.

Moreover, we show that for every positive integer hmlsrc">hImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15003180&_mathId=si2.gif&_user=111111111&_pii=S0012365X15003180&_rdoc=1&_issn=0012365X&md5=1e5dec6f77b9e911c424ea10d625e268" title="Click to view the MathML source">khContainer hidden">hCode">h altimg="si2.gif" overflow="scroll">kh>, there exist graphs with chromatic number hmlsrc">hImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15003180&_mathId=si2.gif&_user=111111111&_pii=S0012365X15003180&_rdoc=1&_issn=0012365X&md5=1e5dec6f77b9e911c424ea10d625e268" title="Click to view the MathML source">khContainer hidden">hCode">h altimg="si2.gif" overflow="scroll">kh> such that for every hmlsrc">hImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15003180&_mathId=si17.gif&_user=111111111&_pii=S0012365X15003180&_rdoc=1&_issn=0012365X&md5=31efaf4b0a808c43715c9eeff713118f" title="Click to view the MathML source">ϵ>0hContainer hidden">hCode">h altimg="si17.gif" overflow="scroll">ϵ>0h>, the value given by our upper bound is at most hmlsrc">hImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15003180&_mathId=si18.gif&_user=111111111&_pii=S0012365X15003180&_rdoc=1&_issn=0012365X&md5=762fd74b9fa6e6ba4e9849d80fae01a0" title="Click to view the MathML source">(1+ϵ)hContainer hidden">hCode">h altimg="si18.gif" overflow="scroll">(1+ϵ)h> times their cubicity. Thus, our upper bound is almost tight.