Packing and coloring r-bounded axis-parallel rectangles

MaRDI QIDQ6356877zbMATH OpenFDO

Authors Marco Caoduro

Publication date 24 December 2020

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Packing and covering in (2) dimensions (aspects of discrete geometry) (52C15)

Abstract: Let $mathcalR$ be a family of axis-parallel rectangles in the plane. The transversal number $au(mathcalR)$ is the minimum number of points needed to pierce all the rectangles. The independence number $u(mathcalR)$ is the maximum number of pairwise disjoint rectangles. Given a positive real number $r$, we say that $mathcalR$ is an r-bounded family if, for any rectangle in $mathcalR$, the aspect ratio of the longer side over the shorter side is at most $r$. Gy'arf'as and Lehel asked if it is possible to bound the transversal number $au(mathcalR)$ with a linear function of the independence number $u(mathcalR)$. Ahlswede and Karapetyan claimed a positive answer for the particular case of $r$-bounded families, but without providing proof. Chudnovsky et al. confirmed the result proving the bound $auleq(14+2r^2)u$. This note aims at giving a simple proof of $auleq2(r+1)(u-1)+1$, slightly improving the previous results. As a consequence of this new approach, we also deduce a constant factor bound for the ratio $fracchiomega$ in the case of $r$-bounded family.

This page was built for publication: Packing and coloring r-bounded axis-parallel rectangles

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