Local and union boxicity

• Published in: Discrete mathematics 2018-05, Vol.341 (5), p.1307-1315
• Main Authors: Bläsius, Thomas, Stumpf, Peter, Ueckerdt, Torsten
• Format: Article
• Language: English
• Subjects: Boxicity; Covering number; Intersection graph; Interval graph
• ISSN: 0012-365X; 1872-681X
• DOI: 10.1016/j.disc.2018.02.003

The boxicity box(H) of a graph H is the smallest integer d such that H is the intersection of d interval graphs, or equivalently, that H is the intersection graph of axis-aligned boxes in Rd. These intersection representations can be interpreted as covering representations of the complement Hc of H with co-interval graphs, that is, complements of interval graphs. We follow the recent framework of global, local and folded covering numbers (Knauer and Ueckerdt, 2016) to define two new parameters: the local boxicity boxℓ(H) and the union boxicity box¯(H) of H. The union boxicity of H is the smallest d such that Hc can be covered with d vertex–disjoint unions of co-interval graphs, while the local boxicity of H is the smallest d such that Hc can be covered with co-interval graphs, at most d at every vertex. We show that for every graph H we have boxℓ(H)≤box¯(H)≤box(H) and that each of these inequalities can be arbitrarily far apart. Moreover, we show that local and union boxicity are also characterized by intersection representations of appropriate axis-aligned boxes in Rd. We demonstrate with a few striking examples, that in a sense, the local boxicity is a better indication for the complexity of a graph, than the classical boxicity.