Boxicity and Maximum degree
| dc.creator | Chandran, L. Sunil | |
| dc.creator | Francis, Mathew C. | |
| dc.creator | Sivadasan, Naveen | |
| dc.date | 2006-10-08 | |
| dc.date.accessioned | 2026-07-07T07:28:51Z | |
| dc.date.available | 2026-07-07T07:28:51Z | |
| dc.description | An axis-parallel $d$--dimensional box is a Cartesian product $R_1 \times R_2 \times ... \times R_d$ where $R_i$ (for $1 \le i \le d$) is a closed interval of the form $[a_i, b_i]$ on the real line. For a graph $G$, its \emph{boxicity} $\boxi(G)$ is the minimum dimension $d$, such that $G$ is representable as the intersection graph of (axis--parallel) boxes in $d$--dimensional space. The concept of boxicity finds applications in various areas such as ecology, operation research etc. We show that for any graph $G$ with maximum degree $Δ$, $\boxi(G) \le 2 Δ^2 + 2$. That the bound does not depend on the number of vertices is a bit surprising considering the fact that there are highly connected bounded degree graphs such as expander graphs. Our proof is very short and constructive. We conjecture that $\boxi(G)$ is $O(Δ)$. | |
| dc.description | 4 pages | |
| dc.identifier | https://arxiv.org/abs/math/0610262 | |
| dc.identifier | http://arxiv.org/abs/math/0610262 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/117883 | |
| dc.subject | Combinatorics | |
| dc.title | Boxicity and Maximum degree | |
| dc.type | text |