Local Boxicity and Maximum Degree

Abstract

The \emph{local boxicity} of a graph $G$, denoted by $lbox(G)$, is the minimum positive integer $l$ such that $G$ can be obtained using the intersection of $k$ (, where $k\ge l$,) interval graphs where each vertex of $G$ appears as a non-universal vertex in at most $l$ of these interval graphs. Let $G$ be a graph on $n$ vertices having $m$ edges. Let $\Delta$ denote the maximum degree of a vertex in $G$. We show that, (i) $lbox(G)\le 2^{13{\log }^{\ast }\Delta }\Delta$. There exist graphs of maximum degree $\Delta$ having a local boxicity of $\Omega (\frac{\Delta }{\log \Delta })$. (ii) $lbox(G)\in O(\frac{n}{\log n})$. There exist graphs on $n$ vertices having a local boxicity of $\Omega (\frac{n}{\log n})$. (iii) $lbox(G)\le (2^{13{\log }^{\ast }\sqrt{m}}+2)\sqrt{m}$. There exist graphs with $m$ edges having a local boxicity of $\Omega (\frac{\sqrt{m}}{\log m})$. (iv) the local boxicity of $G$ is at most its \emph{product dimension}. This connection helps us in showing that the local boxicity of the \emph{Kneser graph} $K(n,k)$ is at most $\frac{k}{2}\log \log n$. The above results can be extended to the \emph{local dimension} of a partially ordered set due to the known connection between local boxicity and local dimension. Finally, we show that the \emph{cubicity} of a graph on $n$ vertices of girth greater than $g+1$ is $O(n^{\frac{1}{\lfloor g/2\rfloor }}\log n)$.

arXiv comment17 pages