Functionality of Box Intersection Graphs

Dallard, Clément ORCID: 0000-0002-9522-3770, Lozin, Vadim ORCID: 0000-0003-2464-7389, Milanič, Martin ORCID: 0000-0002-8222-8097, Štorgel, Kenny ORCID: 0000-0002-1772-7404 and Zamaraev, Viktor ORCID: 0000-0001-5755-4141 (2024) Functionality of Box Intersection Graphs. Results in Mathematics, 79 (1). 48-.

PDF 2301.09493.pdf - Author Accepted Manuscript Download (223kB) | Preview

Abstract

<jats:title>Abstract</jats:title><jats:p>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 <jats:inline-formula><jats:alternatives><jats:tex-math>$$\mathbb {R}^1$$</jats:tex-math><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msup> <mml:mrow> <mml:mi>R</mml:mi> </mml:mrow> <mml:mn>1</mml:mn> </mml:msup> </mml:math></jats:alternatives></jats:inline-formula>, i.e. for interval graphs, and unbounded for box intersection graphs in <jats:inline-formula><jats:alternatives><jats:tex-math>$$\mathbb {R}^3$$</jats:tex-math><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msup> <mml:mrow> <mml:mi>R</mml:mi> </mml:mrow> <mml:mn>3</mml:mn> </mml:msup> </mml:math></jats:alternatives></jats:inline-formula>. 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 <jats:inline-formula><jats:alternatives><jats:tex-math>$$\mathbb {R}^2$$</jats:tex-math><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msup> <mml:mrow> <mml:mi>R</mml:mi> </mml:mrow> <mml:mn>2</mml:mn> </mml:msup> </mml:math></jats:alternatives></jats:inline-formula>. </jats:p>

Item Type:	Article
Divisions:	Faculty of Science and Engineering > School of Electrical Engineering, Electronics and Computer Science
Depositing User:	Symplectic Admin
Date Deposited:	05 Feb 2024 08:52
Last Modified:	15 Mar 2024 16:20
DOI:	10.1007/s00025-023-02075-2
Related URLs:	Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3178377