Local Boxicity and Maximum Degree

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 $\mathrm{\Delta }$ denote the maximum degree of a vertex in $G$. We show that, (i) $lbox(G) \leq 2^{13\log^{}{\Delta}} \Delta$\mathrm{.}Thereexistgraphsofmaximumdegree$\Delta$havingalocalboxicityof$\Omega(\frac{\Delta}{\log\Delta})$\mathrm{.}(ii)$lbox(G) \in O(\frac{n}{\log{n}})$\mathrm{.}Thereexistgraphson$n$ vertices having a local boxicity of $\mathrm{\Omega }(\frac{n}{\log n})$. (iii) $lbox(G) \leq (2^{13\log^{}{\sqrt{m}}} + 2 )\sqrt{m}$\mathrm{.}Thereexistgraphswith$m$ edges having a local boxicity of $\mathrm{\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)$.