Functionality of box intersection graphs

DOI10.1007/S00025-023-02075-2MaRDI QIDQ6140059zbMATH OpenOpenAlexFDO

Authors Clément Dallard, Vadim Lozin, Martin Milanič, Kenny Štorgel, Victor Zamaraev

Publication date 19 January 2024

Published in Results in Mathematics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2301.09493

zbMATH Keywords

box intersection graphsgraph functionalityinterval graphssymmetric differencetwin-width

Mathematics Subject Classification ID

Structural characterization of families of graphs (05C75) Graph theory (05C99)

Abstract: Functionality is a graph complexity measure that extends a variety of parameters, such as vertex degree, degeneracy, clique-width, or twin-width. In the present paper, we show that functionality is bounded for box intersection graphs in $mathbb{R}^1$, i.e. for interval graphs, and unbounded for box intersection graphs in $mathbb{R}^3$. We also study a parameter known as symmetric difference, which is intermediate between twin-width and functionality, and show that this parameter is unbounded both for interval graphs and for unit box intersection graphs in $mathbb{R}^2$.

Recommendations

• Graph functionality
• Graph functionality
• Local and union boxicity
• Grid intersection graphs and boxicity
• Boxicity of graphs with bounded degree

Cites work

• Clique-width for 4-vertex forbidden subgraphs
• Distance-hereditary graphs
• Graph functionality
• Implicit representations and factorial properties of graphs
• On cubical graphs
• Turán-type results for intersection graphs of boxes
• Twin-width II: small classes
• Twin-width. I: Tractable FO model checking
• Zarankiewicz's problem for semilinear hypergraphs

Cited in

(1)

• Graph functionality

This page was built for publication: Functionality of box intersection graphs

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