Tur\'an-type results for intersection graphs of boxes

DOI10.1017/S0963548321000171zbMATH Open1510.05122arXiv2009.04380MaRDI QIDQ6348762FDOQ6348762

Authors: István Tomon, D. D. Zakharov 

Publication date: 9 September 2020

Abstract: In this short note, we prove the following analog of the KH{o}v'ari-S'os-Tur'an theorem for intersection graphs of boxes. If $G$ is the intersection graph of $n$ axis-parallel boxes in $mathbb{R}^d$ such that $G$ contains no copy of $K_{t,t}$, then $G$ has at most $ctn(logn{)}^{2d+3}$ edges, where $c=c(d)>0$ only depends on $d$. Our proof is based on exploring connections between boxicity, separation dimension and poset dimension. Using this approach, we also show that a construction of Basit et al. of $K_{2,2}$-free incidence graphs of points and rectangles in the plane can be used to disprove a conjecture of Alon et al. We show that there exist graphs of separation dimension 4 having superlinear number of edges.

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Planar graphs; geometric and topological aspects of graph theory (05C10) Enumeration in graph theory (05C30) Graph operations (line graphs, products, etc.) (05C76)

This page was built for publication: Tur\'an-type results for intersection graphs of boxes

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