论文标题
本地拳击
Local boxicity
论文作者
论文摘要
一个盒子是笛卡尔的真实间隔产品，其界限是有限的，要么等于$ \ mathbb {r} $。据说，如果最多$ d $限制了一个盒子，则为$ d $ local。在本文中，我们调查了最近引入的图形$ g $的本地框，这是$ d $的最低$ g $，因此可以表示为$ d $ d $ loc的交叉点在某种程度上。我们证明，所有最高度$δ$的图都具有局部盒装$ o（δ）$，而几乎所有最大程度的图$δ$都有局部boxicity $ω（δ）$，从而改善了已知的上限和下限。我们还为局部框架提供了改进的界限，这是边缘数量或属数的函数。最后，我们通过色谱理论的镜头研究局部框。我们证明，本地拳击的图表最多为2是$χ$结合，这意味着该类中的图形的色数可以受其集团数字的函数的限制。这最多可以在拳头图上扩展一个经典的结果。
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 $Δ$ have local boxicity $O(Δ)$, while almost all graphs of maximum degree $Δ$ have local boxicity $Ω(Δ)$, 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 $χ$-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.
