BZPEERSource author record
Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.
Catalog footprint
Published work
We prove that for any triangle-free intersection graph of n axis-parallel segments in the plane, the independence number α of this graph is at least α≥n/4+Ω(n). We complement this with a construction of a graph in this class satisfying α≤n/4+cn for an absolute constant c, which demonstrates the optimality of our result.
Let R be a family of axis-parallel rectangles in the plane. The transversal number τ(R) is the minimum number of points needed to pierce all the rectangles. The independence number ν(R) is the maximum number of pairwise disjoint rectangles. Given a positive real number r, we say that R is an r-bounded family if, for any rectangle in R, the aspect ratio of the longer side over the shorter side is at most r. Gyárfás and Lehel asked if it is possible to bound the transversal number τ(R) with a linear function of the independence number ν(R). 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 τ≤(14+2r2)ν. This note aims at giving a simple proof of τ≤2(r+1)(ν−1)+1, slightly improving the previous results. As a consequence of this new approach, we also deduce a constant factor bound for the ratio ωχ in the case of r-bounded family.
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.