Local boxicity

Louis Esperet (1) , Lyuben Lichev (2)

1 G-SCOP_OC - Optimisation Combinatoire
2 ENS de Lyon - École normale supérieure de Lyon

A box is the cartesian product of real intervals, which are either bounded or equal to $\mathbb{R}$. A box is said to be $d$-local if at most $d$ of the intervals are bounded. In this paper, we investigate the recently introduced local boxicity of a graph $G$, which is the minimum $d$ such that $G$ can be represented as the intersection of $d$-local boxes in some dimension. We prove that all graphs of maximum degree $\Delta$ have local boxicity $O(\Delta)$, while almost all graphs of maximum degree $\Delta$ have local boxicity $\Omega(\Delta)$, improving known upper and lower bounds. We also give improved bounds on the local boxicity as a function of the number of edges or the genus. Finally, we investigate local boxicity through the lens of chromatic graph theory. We prove that the family of graphs of local boxicity at most 2 is $\chi$-bounded, which means that the chromatic number of the graphs in this class can be bounded by a function of their clique number. This extends a classical result on graphs of boxicity at most 2.

Domains: Discrete Mathematics [cs.DM]; Combinatorics [math.CO]

Louis Esperet, Lyuben Lichev. Local boxicity. European Journal of Combinatorics, 2022, 102, pp.103495. ⟨10.1016/j.ejc.2021.103495⟩. ⟨hal-03048296⟩