Local and union boxicity

Abstract: The boxicity

o p e r a t o r n a m e b o x (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

m a t h b b R^{d}

. These intersection representations can be interpreted as covering representations of the complement

H^{c}

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, Discrete Mathematics 339 (2016)) to define two new parameters: the local boxicity

o p e r a t o r n a m e {b o x}_{e} l l (H)

and the union boxicity

o v e r l i n e o p e r a t o r n a m e b o x (H)

of

H

. The union boxicity of

H

is the smallest

d

such that

H^{c}

can be covered with

d

vertex-disjoint unions of co-interval graphs, while the local boxicity of

H

is the smallest

d

such that

H^{c}

can be covered with co-interval graphs, at most

d

at every vertex. We show that for every graph

H

we have

o p e r a t o r n a m e {b o x}_{e} l l (H) l e q o v e r l i n e o p e r a t o r n a m e b o x (H) l e q o p e r a t o r n a m e b o x (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

m a t h b b R^{d}

. 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.

Recommendations

Cites work

Cited in

(8)

This page was built for publication: Local and union boxicity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1709530)