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

DOI10.1016/J.DISC.2015.09.007zbMATH Open1327.05100arXiv1404.7261OpenAlexW2123774049MaRDI QIDQ898085FDOQ898085

L. Sunil Chandran, Rogers Mathew, Deepak Rajendraprasad

Publication date: 8 December 2015

Published in: Discrete Mathematics (Search for Journal in Brave)

Abstract: The boxicity (respectively cubicity) of a graph $G$ is the minimum non-negative 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 (Journal of Graph Theory, 65(4), 2010) that for any graph $G$, $cub(G)le$ box$(G)leftlceillo{g}_{2}alphaightceil$, where $alpha=alpha(G)$ is the cardinality of the maximum independent set in $G$. In this note we show that $cub(G)le2leftlceillo{g}_{2}chi(G)ightceilbox(G)+chi(G)leftlceillo{g}_{2}alpha(G)ightceil$. 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)le2(box(G)+leftlceillo{g}_{2}alpha(G)ightceil)$. Moreover we show that for every positive integer $k$, there exist graphs with chromatic number $k$, such that for every $epsilon>0$, the value given by our upper bound is at most $(1+epsilon)$ times their cubicity. Thus, our upper bound is almost tight.

Full work available at URL: https://arxiv.org/abs/1404.7261

Recommendations

• Cubicity, boxicity, and vertex cover
• An upper bound for cubicity in terms of boxicity
• On the cubicity of certain graphs
• The cubicity of hypercube graphs
• Boxicity and cubicity of asteroidal triple free graphs

zbMATH Keywords

chromatic numberboxicitycubicity

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Cites Work

• Title not available (Why is that?)
• The chromatic number of random graphs
• On the cubicity of certain graphs
• Lower bounds for boxicity
• Cubicity of interval graphs and the claw number
• An upper bound for cubicity in terms of boxicity
• A Constant Factor Approximation Algorithm for Boxicity of Circular Arc Graphs

Cited In (1)

• On the stab number of rectangle intersection graphs

This page was built for publication: Upper bound on cubicity in terms of boxicity for graphs of low chromatic number

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q898085)